It looks like your server is Linux possibly..Apache..running PHP.
If that's the case, you can build a page that you'd like to display for all pages that do not exist and upload it on the server as 404.php or whatever you might want to call it.
Then, add the following line in your .htaccess file.
ErrorDocument 404 /404.php
You are all set.
To me i looks like you are already set or doing this in some fashion. I checked to see if I visit http://www.visitdevonandcornwall.com/test and see what happens.
It gives me a friendly 404 and the HTTP Header is correct.
HTTP/1.1 404 Not Found => Server => cloudflare-nginx Date => Fri, 11 May 2012 17:17:51 GMT Content-Type => text/html Connection => close X-Powered-By => PHP/5.3.6 Expires => Thu, 19 Nov 1981 08:52:00 GMT Cache-Control => no-store, no-cache, must-revalidate, post-check=0, pre-check=0 Pragma => no-cache Set-Cookie => __cfduid=d1b9e2169ed78a6697f752eef1c0a5ee01336756670; expires=Mon, 23-Dec-2019 23:50:00 GMT; path=/; domain=.www.visitdevonandcornwall.com