Terremark's Service Manager for vCloud Express, Kenneth Denson, contacted me this morning over my post yesterday regarding Terremark's billing for opened firewall ports that have no service behind them. He agreed that billing for 2 ports open on a fw with nothing behind them is "silly" and is refunding the May charges.
More importantly, he tried to reproduce my situation, and it sounds like they've fixed the bug - it shouldn't be possible to delete a server when a firewall is configured to send traffic to it.
More importantly still, Kenneth's recently taken the Serivce Manager position, and this was the first time Terremark's contacted me directly since I signed up last year. Hopefully this is a sign of things changing at Terremark's VCE program. I'll probably give them another look next time I'm in the market for that type of service.