Well, you won't believe it, but that hint solved the problem. There was a comment before a line which referred to pam_securetty.so. I checked it out and found that the library was missing (I didn't set up this system in the first place but I actually have to maintain it... :-(
I also thought that PAM wasn't responsible for telnet logins because I got some PAM messages in the syslog output on FTP logins but not on telnet. Now I know better...
Finally, all I had to do was to restore the library and remove the comment. Now it works fine!