tells how to do it, but I'm sure you already know.

And, yes, it should move, not copy, freeing the space from the Exchange server. If it doesn't, better contact the Helpdesk (or however it's organized with you) to find out what's wrong. I think that manually moving should still work. If the criteria aren't too difficult, that's a feasible work-around. For example, if the only criterium is date, than simply sort on date, select all items (select the upper, space-select the lower) and move.
But it should be solvable.