Out of stock products still appear in the frontend

This is actually a feature of Magento.
Setting Display out of stock products to No only hides them from the category list pages and the search results page.
The product page is actually still available.
Starting with CE 1.9.1 there is even a message under the config setting Display out of stock products saying Products will still be shown by direct product URLs..
And this is actually a good thing.
This way search engines don't register a lot of 404 pages when your products get out of stock.
I don't see the harm in leaving it like that. The customer cannot order them anyway.
If you want a product not to be available at all in your store you have to mark it as disabled or set it's visibility to Not visible individually or remove its association to the websites from the websites tab on the admin product edit page.