Evan, this is not a bug. Currently, when a folder is deleted in the web interface, the folder DOES still remain in the file structure. This is because the IMAP implementation needs to remember the UUID associated with this folder. The Restore -> Rebuild feature recursively (if so selected) looks through all the specified folders and restores them. That's why the "ghost" folders return.
We have already planned for the next SM major release to rewrite our handling of removed folders and associated IMAP UUIDs thereby truly removing them from the file structure.
Your customer are safe in re-removing those unneeded, "ghost" folders.