Hi,
We have two HP M476DWs and this gave me some trouble as well. I was able to find a workaround by following the steps below.
1. Navigate to printer's web interface.
2. Click the "Scan" tab.
3. Click "Email Address Book" in left pane.
4. Click "Save/Restore Address Book" button.
5. Make sure "Save the address book to a file" is selected and click the "Save" button.
6. Save and open the .CSV file.
7. Sort contacts to your liking (Make sure ID numbers are still in order) and save file.
8. In web interface, select "Restore the address book from a file", click "Browse" button and select updated .CSV file.
9. Click "Finish" button.
Unfortunately, you will need to do this whenever you add a new contact. Very strange that a simple sorting feature doesn't exist within the web interface, especially when you consider that contacts aren't automatically sorted.
Hope this helps.
Thanks,
Tim