I need to give users rights to do everything except delete messages in my mailbox, but when I remove their Delete rights, they can't move the messages. Does Outlook consider moving a message the same as deleting it?

Yes, moving an item creates a new item in another folder and removes the item from the current folder. Hence, you must grant Delete rights if you want users to be able to move items from that folder. Otherwise, users can only copy items to another folder.