Ok, now the plot thickens a little.
I went looking for the Profile change to update at least my profile and see where it was, so I could pass it on to the original starter of this problem. And its already checked to save my PMs by default. I hadn't changed it, nor, as you can probably tell, was I even aware of that setting.
Shouldn't that have seved the same purpose?
I just tested the PM again, and if I check the "Save to my Outbox" option in ?action=pm;sa=send it saves the message to my outbox. If I leave it unchecked and hope to rely on the profile setting, it doesn't get saved to my outbox.