Magento - Newly created products not showing up in store (Web front end)

I have created a new product from Magento backend but it does not show up under relevant category or in the product page it self. i.e If I type the product url key it goes to a 404 page.

This is just a simple product and I checked the following,

Product enabled : Yes

Visibility : Catalog, search

Product Images : All good

Quantity Available : 9999999

Stock Availability : In Stock

Assign to a category : Yes (I even went to Manage Category to see product is under Category products and its there)

Product in web sites : Assigned

Cache : Cleared 10 X times

I did one more thing I looked at app/code/core/Mage/Catalog/Model/Category.php and add following line in getProductCollection() function before the return $collection

var_dump($collection->getAllIds());

Then I went to the category page and I could see var_dump output all product IDs assign to that category but still new product I is was not there :(

This is really frustrating took my whole day and no luck, any ideas?

Answer