I have been following this but felt unable to make any contribution - waiting to see how things worked out. Do you get this error when you have a message being displayed and you hit the 'trash can' icon? I only mention this because you refer to 'moving' messages to the trash in the way that you might move a message from the InBox to another folder by using 'Edit', selecting the message and then 'Move' and then touching the folder that you want to move the message to...
Also, I probably missed this too, is this a new problem? Or has it always been this way on your iPad. I note you don't have the same problem with your iPhone so, as you suggest, it's unlikely you've got the settings incorrect.
These 'difficult' problems are always the most interesting, so let's keep this going until it's solved.
Tim
Scotland