OK, now I've got it. The problem was in a misconfigured proxy that inserted a bogus Referer header (which is probably used by MediaWiki to detect the need to redirect). So that for a request like that:
GET /wiki/V%E1clav_Havel HTTP/1.1 Host: cs.wikipedia.org Referer: http://cs.wikipedia.org/wiki/V%E1clav_Havel
comes a "HTTP/1.0 200 OK" response with the "page does not exist yet" contents.
After the proxy configuration was fixed, everything works fine.
Thanks for help, -- [[cs:User:Mormegil | Petr Kadlec]]