You did not even specify your Outlook version.
The most frequent question asked about the Outlook Address Book is "why
won't it sort the way I told it to?" Simple answer. Even though we all know
that our Outlook Address Book is simply a view of our Contacts, Microsoft
did not configure it to abide by the settings we chose for our Contacts.
Instead, they hid the sort settings for the Outlook Address Book where no
one could ever find them. Depending on your version and mail support mode of
Outlook, you can sort the Outlook Address Book this way:

98/2000 in Corporate/Workgroup mode:
Tools menu > Services > Highlight the Outlook Address Book service > Click
Properties > Set sort order

98/2000 Internet Mail Only:
Tools menu > Address Book > View menu > Sort by

Outlook 2002/2003:
Go to Tools > E-mail accounts > View or change existing directories or
address books > Outlook Address Book > Change. > Set your sort order there

Note that your options are only to sort by "First, Last" or by "File As." So
if you want your Outlook Address Book to sort by "Last, First," or by
"Company" you must have your Contacts' File As fields configured that way.