Strange - but I want get my 404 Error page working, to get rid of old Google listed pages that are dead

[tl]

Hi

I have a new prestashop site replacing my old website. Google still has old UrLS indexed which people have linked too. I have read to get rid of these I need to get my 404 error page to have 4040 error in the header, as stated here

If outdated pages from your site appear in the search results, ensure that the pages return a status of either 404 (not found) or 410 (gone) in the header.

However my site - (despite what is set in the SEO section of Prestashop admin for the 404.phph page) produces a pretty page that says:

Error We're sorry, but the Web address you entered is no longer available

However it doesnt have 404 error text in the Header or Meta. My template for 404 looks correct having:

header('HTTP/1.1 404 Not Found');
header('Status: 404 Not Found');

However on an error pagwe in the source the only meta is

<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=utf-8" /><meta name="generator" content="PrestaShop" /><meta name="robots" content="index,follow" />

I need to get this working with 4040 error in the header so I can get rid of dead links on google etc.

Hope you can help

[tl]

I have checked a couple of other prestashop sites I have found eg:

http://www.fitness-accessoires.com/lang-en/PrestaShop/sdfgsdfgdfsg

and it seems this is the same on theirs??