we went round this a few months ago
The "autocomplete" in the newer Microsoft e-mail programs doesn't come from the address book - instead a buffer of the last few addresses mailed is held (I think its the last 25 from memory). If the address you're typing doesn't match one of those, then autocomplete doesn't kick in.
In Windows Mail / Live Mail the whole way in which addresses are held is completely different from OE, and to put it bluntly, M$ seemed to have botched it