I can't help explain how Blizzard store their macros but I suffered exactly the same problems last year as I use 2 PCs.

I took it as the final push to move to a bar/macro addon and went for Trinity, now Macaroon, and haven't looked back, using Macaroon for all single and multibox chars.
I now control where my macros are stored, so I can move them around between chars and PCs.
I back the Macaroon files up, so I never lose my macros.
And it helps immensely when setting up a new team... create a Macaroon layout with the basic buttons/macros and then copy the Macaroon file to the other chars, saving loads of time.

Won't help you retrieve your lost macros but will help you never lose them again...

http://www.wowinterface.com/download...-Macaroon.html