You can disable the google enhancement for the 404 page with the web.config setting
<add key="EnableGoogle404Enhancement" value="true"/>
which you could override to false in user.config.
If your skin has the SearchBox instead of just a link that should work on the 404 page.
You could also create a custom 404 page instead of using the pre-made one, you just specify the file with this setting:
<add key="Custom404Page" value="/PageNotFound.aspx"/>
Hope it helps,
Joe