You don't seem to understand... When you view a page with a title that doesn't exist on the database, MediaWiki sends a normal page but with no "content", except the message that says the page doesn't exist yet. And the response is with a HTTP 404 response, so search engines don't index that content and the browser don't cache the page.
When MediaWiki does a HTTP 404 response, that response is intercepted by your web server and instead it sends a custom error page instead of MediaWiki's response.
This image demonstrates that: http://img687.imageshack.us/img687/5548/wikiwithnoacceptencodin.png
You would only see it if you use a browser that doesn't accept compression, or by modifying the HTTP headers, removing the Accept-Encoding one as I did. This is the problem, and it's not caused by MediaWiki but by your webserver.
It has nothing to do with Hebrew or other strange characters. See for example this simple one: . As I said, that only happens when the page doesn't exist on the wiki.
If you're paying for that service you should demand a prompt resolution of this issue. If they're unable/willing to help you I strongly encourage you to find a better service.