Hi,
First of all if your non-existing site results are being displayed in search results(say Google) then you can either demote the sitelinks by going in to the Google Webmasters Tool(go to Configuration -->> Sitelinks)and submit it.
Or, if in your case, it has some links pointing towards it then you can use a 301 redirect and redirect it to your customised 404 page which should could contain navigational options so the users do not leave the given site.
The Web Optimized 404 pages should contain:
- notification that the user has reached a page that does not exist
- a search box
- a easy to understand navigation system so the user can potentially find what they were orginally looking to access
- a link to the home page
If you want to know more, you can check this link on HTTP Status code and see what's best for you
http://www.seomoz.org/learn-seo/http-status-codes
Hope this helps you.
Cheers! 
