MAPIのスタブ（mapi32.dll）を経由するからいけないのであって、直接OutlookのMAPIプロバイダのDLL（msmapi32.dll）をロードしてやればできるんじゃないかと思って試してみたらうまくいきました。本当に大丈夫なのか心配だったのですが、MAPI example code for getting folders and messagesを見ても同じ事をやっているので大丈夫なようです。ただし、OutlookのバージョンによってDLLのパスの取り方が微妙に異なるようなのが面倒です。
で、MAPILogonExしてIMAPISessionを取り出してIMAPISession::OpenAddressBookを呼び出してIAddrBookを取ったら後はWABの場合と同じかなと思ったら、やはりこの場合もOOMのAddressListから取り出すのと同様、一つのアドレスが一つのエントリになってしまっていました。WABの場合には、PR_CONTACT_EMAIL_ADDRESSESを指定してプロパティを取り出すと一つのエントリから複数のアドレスを取り出せるのですが、Outlookではそのプロパティは存在しません。このあたりの動作はWABとは違うようです。
というわけでちゃんとエントリを取り出したかったら、IMAPISession::OpenMsgStoreしてIMsgStoreを取り出し、IMsgStore::OpenEntryして連絡先フォルダのIMAPFolderを取り出しフォルダ内のエントリをなめていく必要があるようです。面倒だし（QMAIL的には）見た目は変わらないのでIAddrBook経由でも良いかも。