Thus far they don't delete tweets from the search results even after they have been deleted within twitter itself, so I suspect they are append only as you suggest.
It's frustrating that search includes deleted tweets. It's depressingly often for me that a Twitter search results page has at least one duplicate result because someone posted twice to fix a typo.