Just some clarification (I think this is correct)...
Windows Mail - Client only with Windows Vista
Windows Live Mail - new client for Windows 7
Windows Live Hotmail - new Hotmail (not a client).
I think if you install Windows Live Mail it will copy contacts (but not sync) contacts from Windows Mail. So it looks like sometime Windows Live Mail was installed on the same machine as Windows Mail, so when Windows Live mail was accessed from another machine the contacts from Windows Mail were visible.
Plusnet Plusnet Pro 21CN Netgear DGND3300v2 router
Windows XP Pro SP3