However, assuming that is the case for some people, we have to look elsewhere than the last login lookup. There are only a few other usages of quietlog: motd (open file, read it), mail (check environment, stat file), and pam_silent.
The first two are not going to cause any kind of performance issue, so we have to look at pam_silent. This variable is particularly interesting, as it is only set to 0 if -q is not passed (and it is not) and there is no .hushlogin (it is not directly controlled by quietlog).
If it is not 0, then it is left at a default value, which is PAM_SILENT, and is passed to almost every single PAM function. It could very well be that there is some crazy-slow logic in PAM that is activated if you do not set PAM_SILENT.
Given this, someone experiencing this issue might look through the code for PAM to see if anything looks juicy (and this is something that will best be done by someone with this problem, as it could be that they have some shared trait, such as "is using LDAP authentication").
(edit: FWIW, I looked through OpenPAM, and I am not certain I see any actual checks against PAM_SILENT at all; the only mentions of it are for parameter verification: the library makes certain you don't pass unknown flag bits to anything.)