The lastlog and faillog files deliver inadequate performance when there are UID numbers in the >500,000,000 range. A test on a Pentium-M 1.7GHz showed the "faillog" program taking over a minute of CPU time. faillog is in the shadow-utils package but I'm filing the bug report against pam because of pam_tally.so and other modules that use it. A hacky solution would be to have the same format of the faillog and lastlog files (with holes) but to have a hash table in a separate file that indicates which parts of the files are not holes. I think that the best long-term solution is to migrate to a new file format and break compatibility (as we did with utmp).
I second the motion to have a non-sparse representation of "faillog". For problems with the sparse representation of "lastlog", see bug#146214.
pam_faillock uses a different data structure - a file per user in a /var/run/faillock directory. This should be reasonably scalable.