You may want to quit Mail while doing this, as I'm not sure what might happen if you don't.
The ~/Library/Preferences/com.apple.mail.plist file is binary, so you have to use the Property List editor (installed with XCode) to open it. Once it's open, navigate to Root -> Mail Accounts. In there you will see numbers, each of which is an e-mail account within Mail. Inside each of those numbers should be a string value called SentMessagesMailboxName, which defines exactly what it says. Change it to whatever you like. I changed it to the default folder name that the web-interface uses, since that is not configurable and is handled on the server which is beyond my control.
Now, whenever I send mail, it gets saved into that folder. You could then move the contents of your "Sent Messages" folder into the current one, then delete that original empty folder, and you'd have one less place to dig through while searching for that lost message.

