My guess (though I do not know Outlook very well):
a. The Address book only shows entries that have an "e-mail address". But
there are different types of e-mail address in Outlook - an ordinary e-mail
address shows up as type SMTP and a FAX e-mail address shows up as type FAX
b. Outlook creates FAX type e-mail addresses when you enter an address in a
Fax number field in Outllok contacts
c. when you sync your data with Salesforce, it's possible that the contacts
created do not have these fax addresses set up.

I would guess that if you open one of the contacts that does not appear in
the list, and save it (or perhaps, make a change to it and save it) Outlook
will probably set up the fax address and the item will appear in the list.

However, even if that works, I don't know whether there is an easy way to
update all the affected records, other than to write a macro in Outlook to
do it. You may find out more in an Outllook group.

Peter Jamieson