I don't know if this is good or bad news, but apparently if you have ÜberTwitter you get to read any tweet once it get download into by ÜberTwitter client even if that tweet is deleted.
ÜberTwitter doesn't use PUSH technology. That's why the client needs to set the interval checking time to refresh the tweets every minute or so. If that interval is very small it will drain your battery but you will get to see maximum number of deleted tweets.
Let me give you an example, lets say that you tweeted something and the next 5 second you changed your mind and deleted that tweet. In this 5 seconds, all your followers that use ÜberTwitter client who managed to download that tweet to their Blackberry will read it even after 5 hours, because Ubertwitter won't bother looping through your cache and delete that tweet. Unless they manually clear the cache.
I don't know about other clients though, you can help us.