I've seen several machines within the past two days experiencing this issue.
I can tell you that the problem seems to exist using the following:
1) 64-bit Windows Vista Business/Enterprise/Ultimate or 64-bit Windows 7 Professional/Enterprise/Ultimate
2) Outlook 2007 (regardless of Service Pack or hotfixes)
I used a 32-bit Windows 7 Enterprise virtual machine, set up my company Outlook profile, Windows Fax and Scan, and it was able to pull my Outlook Contacts by default.
In every 64-bit environment, no dice.
I did a comparison between two Windows 7 "Default Programs" list in the control panel (one x86, the other x64). All Default Programs and protocols for Microsoft Outlook and Windows Contacts are identical!
One would think that this would have nothing to do with Default Programs at this point, and I tend to be "one" here. I think it's just simply Windows Fax & Scan x64 being unable to communicate with Outlook 2007 x86.
...but let's take this experiment a bit further, shall we?
With the Office 2010 Beta being available in 32-bit and 64-bit flavors, I decided to install the 64-bit version on Windows 7 x64. Pull up company Outlook profile, fire up Windows Fax & Scan...no love.
So apparently, either the 2010 Beta has problems talking to WF&S or WF&S x64 just has problems with Outlook altogether...