Could be something to do with the contents of your .httaccess file, especially if you are using any 301 redirects.
On your web server, try renaming .htaccess to .htaccess.old and retry the McAfee verification.
If that works then follow the verification process then at the end rename your .htaccess.old file back to .htaccess
It worked for my site and I do make use of 301 redirects.
If you're interested in testing the header response to a 404 request on your site the easiest way is to download a copy of curl for your OS and at the command line type:
curl -s -D - -o /dev/null http://gravitationalfx.com/there-is-no-spoon
substituting your own domain name and non-existant web page to force a 404.
Here's the response I got using curl.exe on Win 7 64-bit:
HTTP/1.1 301 Moved Permanently
Date: Tue, 10 Aug 2010 14:51:21 GMT
Expires: Wed, 11 Jan 1984 05:00:00 GMT
Cache-Control: no-cache, must-revalidate, max-age=0
Last-Modified: Tue, 10 Aug 2010 14:51:22 GMT
Content-Type: text/html; charset=UTF-8
It was apparent in my case that the header was returning a 301 redirect and not the expected 404.
If this doesn't help, then please check your plug-ins for any type of redirects. This could also include a search redirect.
I noticed that for the classifiedsup.com website which somebody mentioned further up the post, it redirects any 404 requests internally to a google site search and hence returns a 302 header for the redirected search page. This is also a form of redirection and disabling the site search plug-in will allow for McAfee verification.
Again, curl pointed to the culprit i.e.
curl -s -D - -o /dev/null http://classifiedsup.com/nobody-here-but-us-chickens-cluck-cluck
HTTP/1.1 302 Found
Date: Tue, 10 Aug 2010 15:24:18 GMT
Server: Apache/2.2.3 (CentOS)
Set-Cookie: SESS772e044315b2861d06cea0f3074c3bb4=v5hf3t51iperfu22smm0jcacu0; exp
ires=Thu, 02-Sep-2010 18:57:38 GMT; path=/; domain=.classifiedsup.com
Expires: Sun, 19 Nov 1978 05:00:00 GMT
Last-Modified: Tue, 10 Aug 2010 15:24:18 GMT
Cache-Control: store, no-cache, must-revalidate
Cache-Control: post-check=0, pre-check=0
Content-Type: text/html; charset=utf-8
If you're unsure about which plug-in may be causing the problem,
1. rename the .htaccess file anyway
2. disable all plug-ins
3. run the McAfee verification process
4. enable plug-ins
5. rename .htaccess back
Curl can be downloaded from:
Hope this helps y'all.