I have definitely have experienced problems like this. Not just because the merchant interface said they would be 'searchable soon', but because product would literally not show up in Google Shopping for many hours after upload.
I think it was partially due to the size of the feed (30,000 products), and partially due to some of the products coming under extra scrutiny on each upload.
Either way, moving to uploading every 4 days did seem to help quite a bit. Only thing to keep in mind is that if you update prices on your site frequently you need to upload products to google just as frequently, the prices must match.