You never did mention the brand of phone you have? I believe there is a setting on most servers and devices, to either delete from both server and device, or just delete from device and keep a copy on the server
The HTC P4000 I mentioned above is my brand of phone. It is on the Telus network, if that is what you mean.
I assume it must be a device related issue since I don't have this issue come up when I use my home computer, laptops or work computer.