Several people I know have complained about the fact that MSN Messenger personal messages seem to "revert" back to what they used to be after a while.
From what I've observed, the personal messages are saved on the computer, NOT on the MSN content servers (like your MSN name and contact list are). I occasionally sign on to MSN using other computers and whenever I do so, I sign on with the MSN personal message I had last time I used them.
Furthermore, the personal message is only actually "saved" when you exit MSN manually. (Again, this is just from what I've observed.) If you shut down the computer, leaving MSN open, MSN usually does not save the PM. Try right-clicking the taskbar icon, then hitting Exit - it should save then. This has worked for me every time I've tried.
Not that I care all that much about MSN PMs, or anything.