Hi,
don't know if you still have this problem (if not I leave this note as an information source), but I was able to get around this bug (same setup, vb6 + Outlook 2003 + Win7) by adding the line
MapiMeassages.RecipDisplayName = "Somebody" ' (<- fill in your recipients name)
before a call to MapiMessages.ResolveName (or even before MapiMessages.AddressResolveUI). If this does not work, try to REM the lines AddressResolveUI and/or Resolvename. If the recipients name is not known, you can simply repeat the recipients email address, but DON'T leave this field empty.
HTH
Andy