Earlier quoted context omitted.
I'm pretty sure that the iPhone asks you if you want to keep a local copy of your contacts & calendars when you remove an Exchange account, so you may have hit "No" on accident.
It didnt on my old iPhone 3G. Gone were all my contacts and calendering data, including birthdays. I had to export my stuff to CSV and massage it in local Outlook and do some reverse-and-double-wipe sync stuff through iTunes. It was horrible and I refuse to buy another iDevice ever again.
This kind of behaviour is probably something businesses like. Info on company servers stays on the servers.
This isn't an "iDevice" issue, it's a data ownership issue.