Can you check how is configured this value?
System -> Configuration -> Catalog -> Inventory -> Stock Options -> Display Out of Stock Products
Maybe you're hidding out of stock products.
Hi Damian,
"Display Out of Stock Products" is set to "Yes" - So it is not that :-(
Edit: Also, simple products that are not in stock will show up as "Not in stock" on frontend, but when it's a configurable product version, then it'll just dissappear.
Did you ever get a solution for this? I have the same issue.