@Pekka: Yes. On newest browsers any URLs has UTF-8 encoding. And they rewrites domain.com//контакты to domain.com/контакты, like it is excepted to be.
As far as I know, this is not entirely correct and this may be the reason why it doesn't work for you.
What new browsers are really doing is they show you the URL in its native form контакты
, but internally still make the request in percent encoded form.
This seems to be the crux: You type something in, IE recognizes the Unicode characters, but the subsequent 301 redirect leads to a (correct) percent encoded URL. A modern browser will automatically "decode" the percent encoded URL; IE and older browsers might not.
I don't know whether there is a workaround for this. One thing you could try is have a PHP script do the URL rewriting, and have that script redirect to the (however invalid!) URLDecoded URL:
<?php header("location: http://example.com/контакты"); ?>
I have no idea whether this'll work, though.
Reference: Unicode characters in URLs
Related IE setting