if you tried everything, but is not work try this:
Go administration-> menu, if do not have "HOME" line add it.
Name: Home, Class: AdminHome, Status check show, Parent: Home.
I have presta 1.5.4. I set in product page Visibility "Nowhere" but product appear in front office same visibility is set "everywhere".
Not solution to this problem?
Disable product is not good from SEO.