Adele,
The Outlook "From" field sorts by display name using a literal alpha sort (numbers/symbols, small letters, then Caps, I believe the order is), not by email address. Different companies use different display name styles such as "Lastname, Firstname" or "Firstname Lastname"-no comma. If he's trying to sort by last name, those display names that come across via Internet from other companies may not sort by your company's standards.
You may try going into Field chooser (right-click the bar with the From field) and try adding Internet Account (left click and drag to add to current fields. I have been told this lists actual email addresses and he may get a more accurate sort by left clicking this field.
If this doesn't work, note what display names don't sort properly and see if there is a common denominator such as symbols, spaces or un-capitalized letters that might be the cause. Unfortunately, there may not be a fix other than to choose a different field to sort by.
Hope this helps.