It depends on your situation.
Your PHP could also handle the lack of database connection in a nice way. But if you have a custom PHP with many possibilities for bugs and problems, go for an HTML page.
If you're using a system such as Drupal or WordPress it's best to go with whatever is provided there, possibly adding something such as a module such as Search 404 on Drupal that will take your visitors to a search page.
If you have a lot of traffic and the load on your servers might go up considerably when suddenly hundreds of people are refreshing a page it can be an idea to serve an image instead, served from a 3rd party service (e.g. Amazon) since it will take people more time to load the image and it will keep them from hitting Ctrl-R very quickly which would cause your load to go up even more.