Lookup Previous is OK, but doesn't always give me what I want. For example, if I create a new Contact record, then move to another record, I can't use Lookup Previous to find the new one since it wasn't selected from a lookup in the first place. In any case, Lookup Previous requires 2 clicks, and click are precious in a busy environment.
What I would prefer is a list of the last 10 Contact records I have viewed in the Nav bar as hyperlinks. One click and you have the record you want.
The same "Last 10 Viewed" could also apply to Company records, Group records, Opportunities, and Tasks.