Thank you for answer!

Odd's are good it's not you. Tried it from other locations (such as a system at the library, etc.)?
I've tried it from my desktop and from my server. I have WXP installed on my desktop and on server there is a slackware. But I haven't tried it from completle another location. But my friend tried to log from his home and he succeeded. I'd try today from my other client and let you know.

Well, I guess you have to consider if it's worth it to you. Ask yourself: How much time are you going to spend dealing with this hosting provider, trying to resolve issues that you should never see with a properly configured and administered host? Are you billing for all of this time? Is it worth it, even if you ARE billing? Is your client getting what he paid for? I'm curious who this ridiculously inept host is. You don't have to tell (names changed to protect the guilty and all that), but it would be interesting to know.
It's definitely not worth to me. But problem is that - client has already paid for a whole year. I haven't seen the contract, but I doubt there is and offer for mod_rewrite etc., so the contract probably can not be canceled due to unsufficient services.

So the soulution would be probably - stay this year. And as soon as possible change the hosting company. I have one favourite hosting that I reccomend to my clients so... But the last verdict is up to my client.

And btw try www.n-r.cz - you will be surprised