I ran across these error pages as examples of a, er, better way of doing it.
First: gaeb.teattime.com/notfound.html Nice graphics, no more useful than the original 404 message, but nicer to receive.
Second: cold-dead-fish.com/404.asp Direct, and to the point. If you aren’t thick skinned you have no business surfing the ’net anyway.
Finally: mcsquared.com/error1.htm Fantastic. A sense of whimsy and humor. An excellent waste of time, resources, and bandwidth.