Using IMAP, how can I figure out if a mailbox has been moved or deleted by another client?
The LIST command simply does not list a deleted mailbox any more.
Exactly. You have to remember what folders you know about. Next time you do a LIST, any that are missing have been deleted.
Additionally, you should be tracking every folder's UIDVALIDITY value. If it changes, that folder is not the same one you know about. It may have been renumbered, deleted and recreated, or deleted and replaced by a renamed folder.
In either case, you should dump any cached information you know about that folder.
There is not, in general, any way to track folders that have been renamed by another client. You can only detect that a folder is missing and there is a folder with a new name. IMAP simply does not provide enough information to correlate them. Tracking messages and folders across moves does not appear to have been a design goal of IMAP.