We got a lot of complaints about this and the fix wasn't entirely obvious (to me at least), so that's why I'm documenting it here.
As you can see, the problem wouldn't be so bad if all of our contacts came from the same company - but they don't. Our contacts come from lots of different companies.
So, how do we change this?
In your Notes client, click on File, then Preferences.
In the left hand panel, click on Contacts.
On the contacts screen, change the type-ahead option drop-down to display Internet Address (or you could use company name which is quite useful too).
The effect should be immediate, so try starting a new email and typing a first name (then push comma) and see what happens.
PS: Big thanks to Daniel Lechner and Sunanda A Patil for pointing this out to me.