That doesn't sound right. If you read this third-party analysis (below sponsored by RIM), it shows that a BlackBerry keeps a constant "server connection" when waiting for information, too.. Just like an iPhone. The analysis shows that RIM sends the device a UDP packet to initiate a fetch, not a SMS message.
Basically, the assessment shows that RIM is significantly more efficient all-around in how it does push (as compared to Microsoft's Direct Push, which is used by Exchange Servers).
http://na.blackberry.com/eng/ataglance/get_the_facts/Rysavy_Email_Efficiency_Study_2008.pdf
That's how RIM does it too. Deletions are sent to the server the next time the BlackBerry talks to the server (i.e. gets a new email), or after 20 minutes, whichever happens first. It doesn't just waste battery calling out to the server every time you delete something.