That is a strange error, I've certainly never seen it before. Could have been caused by some IIS module like the IIS url rewriter if they had some strange rule configured it would be altering the requested urls before they even got to the mojoportal url rewriter. Other than that I would have been looking in the database to see if somehow that strange character string had gotten into the data for the friendly url mappings. Probably was some IIS module configuration though that your host made not thinking it would break anything. I'd be interested to hear it if they do offer a good explanation.
Best,
Joe