I assume you mean when composing? (aka you don't want to go to to the addresses tab first)
Are they already sorted by address book though? When composing click on 'To:' make sure contacts, or personal & shared contacts is selected then at the search bar put in:addressbook (followed by a name if you want to narrow the search).
-Unfortunately that tiny search bar doesn't work exactly like the main search bar, it doesn't search minor fields at present.
+ don't most companies use one common domain...(ya i know-set personal email addresses aside for a sec)
No one made an RFE (
/forums/developers/9966-problem-about-new-messages.html) to ehance 'show names from:' (after you click 'to') to include a list of your address books. Right now there's just 'contacts' or personal & shared contacts' or 'global address list' drop downs. Ie if you select contacts it should then show you a address book drop down.
-Though I would just see where this is at after v5 comes out, as a lot of address book stuff is being totally redone in terms of organization/layout.
Your idea would be to put headers (saying by company is too narrow-someone might not care about that field so we'll say by address book name) between contacts when using autocomplete or any address search.
The problem is, you want name relevance first, so instead do this: add the address book it's contained in to the autocomplete, there's plenty of wasted space after the name/email address anyway.
-Of course draw me a diagram/screenshots if I'm totally off what your asking
So autocomplete results would look like:
First Last <first.last@domain.com> - in:AddressBookFolderName
Because for those using higher resolutions, the autocomplete just has wasted drop down area that could be put to use.
If you want-go ahead and make the RFE's out of any of these ideas.
Bugzilla
Wiki
Source
Contacts list Arrangement 
Linear Mode
