Do you have a 404 error page setup? WordPress has already a simple message that is shown within the templete, so the visitor doesn’t feel lost and can get back to where they want.
If you want to change it with your custom message, edit the index.php file under your theme directory. In the file search for “Sorry, but you are looking for something that isn’t here.”. Replace it with any text you wish or you can add an image if you wish.
Anne Zelenka wrote a little post about the 404 pages, the good, the bad, and the poetic.
I didn’t think some sites were so creative. Take a look.