However, it's hard to believe that a
hosting provider would include this in
their default 404 page if it was
Don't be so sure - I was with a very reputable host (or so I thought) who got hacked due to an unpatched vulerability and every single site on the host was deleted by the hacker. Their response - roll back to the last backup (72 hours old) and hope nobody notices.
That said, there have been 404 XSS attacks in the past but they usually only affect a single piece of software, not an entire system. I don't know how including the URI would affect such an attack though.
The ONLY thing I can think of, is if your web host was really poor, and I requested
/gimma404.html?'); DELETE * FROM Users; -- and somehow the RequestURI was logged into a database and not escaped then you could have an SQL Injection attack.