That does not sound like a lot of options that should cause this problem.
It could be that there are orphaned Options in the options table, or orphaned products in the products table.
How many records are there in each of those tables?
Your product results page only shows 17 products.
each advanced option you create will effectively add another product record. that's about 60 more records for the product combination's you describe which is nowhere near the 5189680040 that go daddy is claiming.
Simple options should be used for any options that do not need to have a unique description, SKU or price.