Wow, all those views, and no ideas huh?
Heres what I (we) know so far:

NOT policy related (or shouldn't be, no local policies set, and passwords stick when profile is setup on another workststion)
Affects XP only so far
Registry keys created when saving password still exist after reboot
keymgr.dll shows no entries after reboot, entries show up prior to restarting
Permissions changed from only System to Full for user for that registry key, no effect after reboot
Only effects a small handfull of users, no similar extra software installed on all effected machines, same services startup, etc.

C'mon guys, I'll try anything to find the cause, ANY idea is a good one at this point.