As of today Jan. 2010 the problem described still exists.
Server=Mercury/32 v4.72; client=Thunderbird 3.
I could find only one solution to prevent the name of a deleted IMAP folder to reappear forever: edit manually IMAPSUB.PM in the MAIL dir on the server and remove the line corresponding to the deleted folder.
1) I also saw a similar problem revolving around the management of IMAPSUB.PM: I move a message-only folder under a folder-only folder, then it is impossible to subscribe to it. I.e, I subscribe, it shows up, next time I start TB it is gone, must subscribe again.
Cause: IMAPSUB.PM was never modified by my subscription. Yet the account running Mercury/32 has all rights on that file.
2) The renaming of a folder-only folders is also not working (message-only folder can be renamed though): it is refused by the server.
3) the similar issue described in thread http://community.pmail.com/forums/thread/21215.aspx is also still relevant today.
4) the issue on hierarch.pm described in thread http://community.pmail.com/forums/thread/2634.aspx of 2007 is also still relevant today: yesterday I saw that all IMAP sub-folders containing messages were moved (by Mercury?) under Mailbox, the tree structure still appearing in IMAPSUB.PM but emptied.
I.E. all folders in hierarch.pm appeared as :
0,0,"38488A1:165E:FOL0027E","231A164:My Mailbox",...
JF