We are experiencing this issue as well. I have a ticket # that I opened to day with support for our commercial internet account.
The hijacking is specific. It only redirects when it detects specific useragents, and it appears to be whitelisting major domains. IE I cannot get a 404 error on google.com, youtube.com, digg.com etc. But every single 404 error on my personal websites and company servers which actually returns a 404 header response gets redirected.
== Mimicking a standard Mozilla user-agent ==
C:\>curl --trace-ascii dump.txt -iL http://login.myinnsite.com/notf
ound -H "Accept: text/xml,application/xhtml+xml" -H "User-Agent: Mozilla/4.0 (co
mpatible; MSIE 6.0; Windows NT 5.0)" -H "Cookie: innsiteLocationPlan=0"
HTTP/1.1 200 OK
<HTML><script>window.location='http://assist.mediacomcable.com/mediacomassist_pn
f/dnsassist/main/?domain='+escape(window.location);</script><body>The Search Gui
de redirection service has been enabled to provide helpful searches from browser
queries. You entered a non-existent url and your browser attempted to redirect
you with Javascript. To enable this please update your browser preferences. <a h
ref='http://search.mediacomcable.com/prefs.php'>To turn off this feature please
click this here</a></body></HTML>
== Not mimicking user-agent ==
C:\>curl --trace-ascii dump.txt -iL http://login.myinnsite.com/notf
ound -H "Accept: text/xml,application/xhtml+xml"
HTTP/1.1 404 Not Found
Date: Mon, 31 Jan 2011 21:50:27 GMT
Server: Apache/2.2.11 (FreeBSD) mod_ssl/2.2.11 OpenSSL/0.9.8e DAV/2 PHP/5.2.8 wi
th Suhosin-Patch
Content-Length: 206
Connection: close
Content-Type: text/html; charset=iso-8859-1
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<html><head>
<title>404 Not Found</title>
</head><body>
<h1>Not Found</h1>
<p>The requested URL /notfound was not found on this server.</p>
</body></html>
EDIT: It appears that any 404 error/page with a <meta name="generator" /> in it does not get hijacked. So wordpress and other 404 errors which include a generator value are not hijacked, but default server 404's are.
So Mediacom is filtering 404's without a "generator" and match most major user agents, while whitelisting major domains like google.