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.