Somehow, after updating my iPhone to 2.2 the "advanced" settings of my IMAP accounts were set to store Sent, Draft and Trash on the iPhone, instead of the mail server. This resulted in the "cannot move to trash" error in my previous post.
I've never seen this option before, maybe it has always been there, maybe the default has changed in 2.2. But once I set everything to be stored on the server (trash, drafts, sent), it worked as before. Anyone?