Picked up a Google-safe way to redirect a no-longer existing page with a header 301 redirect in PHP today. GoogleGuy confirms that it's valid and won't cause problems with the Googlebots.
In short, just use:
header("HTTP/1.1 301 Moved Permanently");
header("Location: http://www.newdomain.com/newpage/newurl.htm");
exit();
Now I know some may think I'm making too much out of the 'Google-safe' thing, that I should just run my site any way I want to run it.
I like Google, though. I like that it sends new people to my site. I like to try to make sure things I do on my site don't dramatically affect the way Google sees and indexes me.
Call me crazy if you like, but it's the way I see it.