I've been working on a HP machine that would error out on Windows Mail indicating the message store was bad and because of MSOE.dll was corrupted. Went around the block a few times and finnally decided to install Live Mail which failed to open because it said the calendar contains corrupted data.
Anyhow a while back the owner migrated their hard drive to a larger one and I never tied the two things together. Apparently HP has a Intel Rapid Storage Technology driver update (SP47845.exe) that fixes the problem...it did mine. Afterwards both Live Mail and Windows Mail work just fine.