Hi Joe, since I was working with PageNotFound.aspx, there seem to be a couple of issues with it. Under IE 8, I can't see the Google search box at all, and I get the following error logged by the browser:
Webpage error details
User Agent: Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; Tablet PC 2.0; .NET4.0C; .NET4.0E; InfoPath.2)
Timestamp: Thu, 10 Jun 2010 20:31:55 UTC
Message: Unknown runtime error
Line: 85
Char: 400
Code: 0
URI: http://linkhelp.clients.google.com/tbproxy/lh/wm/fixurl.js
I also tried using the baked-in Google search functionality under Firefox (which doesn't complain about the JavaScript), but it seems to be busted as far as I can tell. To replicate, try this:
Navigate to http://www.mojoportal.com/blahgs.aspx, and you'll get the 404 page.
Enter "blog" in the search box and hit submit. You're returned to PageNotFound.aspx, with "PageNotFound" now in the search box.
Is there some configuration that needs to be set, or is this a true bug?
Also, if you need to overhaul this page to fix something, would it be possible to optionally use the internal site search functionality in place of Google search? I figure there's really no need to involve Google in this transaction. 
Thanks,
Jamie