I created a new folder in Outlook, it became visible on my iPhone and later I removed the folder. The folder stayed in the iPhone and worse, duplicated in the Trash folder. I emptied the trash, but after more than a day, both versions of the original folder are still on the iPhone.

Holy shit batman! I rebooted the device, but no good. So, I deleted the Exchange account and set it back up again. This was a real pain in the butt.