Can you give us some figures related to the scale of your problem?

How many users in /etc/passwd ? Or are you also interested in deleted users?
How many day-to-day users?
How big is this wtmpx file ? Size unformatted and number of lines formatted?
How old is this wtmpx file? (Look at the first few records with fwtmp).
How powerful is the computer?

My usual approach is to break the wtmpx file into separate years and then use "last -f filename" in descending year order until we find the real last login. Obviously the day-today active users will be in this year's file by now. The "last" program itself reads wtmpx files backwards which is why it is so fast for active users.
We would use the "-n 1" parameter to "last" because we are only interested in the last login (this saves a lot of processing).

As your project design evolves, will you be running this report regularly? If so, it would be a good idea to consider starting a new wtmpx file regularly (and keeping the history if you need it) or even using a simpler system of recording the last login in the user's home directory.
I prefer the system of recording the last login in the user's home directory and then locking the account after 3 months non-use - or immediately if the user leaves the company. Unless your system allows significant disc space usage in user home directories there is no harm in just locking the account rather than deleting it. That way you will never get two different people with the same login account name and simple mistakes like Maternity Leave are easy to fix.