I assumed that deleting the message in Evolution would also delete it from the server.


Um, no. That would be a bad assumption.