Hi,
I'm not sure, but I suspect the new Snow Leopard feature ...
http://www.apple.com/macosx/refinements/enhancements-refinements.html#mail
... that lets you move folders around manually might be what's causing the weird behavior.
In Leopard, you could move a folder inside another folder but, otherwise, they would always stay in alphabetical order, I think.
Anyways, in Snow Leopard (and Leopard for that matter), there's an invisible file around ~/Library/Mail/<name of your email account>/.mboxCache.plist It seems to keep a list of the mboxes in that folder/account. In Snow Leopard, the first time you manually move an mbox out of alphabetical order, a new key called MailboxDisplayOrder seems to get created in that plist for all the existing "non-special" (i.e. not INBOX, Sent, Drafts, etc.) mboxes in that folder. Once that key exists, it seems like new folders get appended to the end of the order.
I don't know the right way to fix the problem though. I'm really just posting my observations, based on what I'm seeing on my computer. I'd be very careful about manually messing with invisible files in your mail, especially if you don't have a good backup. (No idea if you can restore an invisible file with Time Machine.) A lot of this is guesswork. But I thought maybe it'd help someone.
Later,
k