Have you checked the settings at Admin > Configuration > Maximum Values > New Product Listing - Limited to ...
to see if your listing is actually being limited to recently added products instead of all products?