lammert - 10:10 am on Jan 24, 2011 (gmt 0)

Hi ecochild, first of all Welcome to WebmasterWorld!

Yes, returning a 404 is OK, Google and other search engines should interpret that correctly. If there are no links to those pages it may take a while before the search engines have found all those return codes, because spidering frequency is often a function of the popularity of a page. To speed things up in Google, you can go to Webmaster Tools and mark those specific URLs for deletion from the index.