Look at the code for getlastlogxbyname(). It does an ASL query for last login, and that's the source of the delay.
http://www.opensource.apple.com/source/Libc/Libc-763.12/gen/...
(edit: I have gone ahead and verified your statements regarding getlastlogxbyname now being based on ASL. Using that knowledge, and based on st3fan's comments about the output of dtrace, I then used dtruss to verify my own assertion regarding the order of events. The result: .hushlogin in fact only affects the output of "last login"; it does not keep login from getting that information in the first place with ASL. To keep it from doing so you must pass -q, something Terminal does not do.)
The correct way to bypass the ASL query is to set Terminal to open shells with /bin/bash (or your shell of choice) instead of the default login shell. Terminal will still use /usr/bin/login to launch the shell, but it passes the -q switch to prevent the ASL query.
When I dug into the source code a couple of months ago, I inadvertently made both changes (Terminal settings and .hushlogin). Clearly it's the Terminal settings that solved the problem and not .hushlogin. Thanks for clearing it up.
(edit: I have gone ahead and checked: thought_alarm is correct, in that getlastlogxbyname is now using ASL instead of utmpx; however, I have also verified my sequencing assertion with dtrace: .hushlogin has no effect on the usage of ASL, but manually passing -q to login does: it thereby cannot be the source of a .hushlogin-mediated delay.)
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.)
0) `login -pf`
1) quietlog = 0
2) if ("-q" in argv) quietlog = 1
3) if (!quietlog) getlastlogxbyname(&lastlog)
4) if (!quietlog) quietlog = access(".hushlogin") == 0
5) dolastlog(quietlog) ->
6) if (!quietlog) printf(lastlog)
You can see from this that the "searching the system logs" (which, to be clear, is going to be really really fast: /var/run/utmpx is a small file with fixed length fields) happens in step #3, before .hushlogin is checked in step #4.
If you wish to verify, you can read the code at the following URL. Note that __APPLE__ and USE_PAM are defined for the OS X distribution of this code, while LOGIN_CAP is not.
http://opensource.apple.com/source/system_cmds/system_cmds-5...