Right, I understand. That’s definitely an issue, as we require deleted messages to be deleted in your apps per the Developer Policy. You should either be listening for deletion messages on the Streaming API and removing them from your data store as this occurs, or checking for the current status before displaying them in your app by making calls to request them and check for not found messages. That might be difficult given rate limits if you’re not listening on the Streaming API.
In general you should store the Tweet IDs rather than the whole Tweet content as then you won’t be at risk of displaying deleted Tweets - you can request the Tweets by ID (e.g. using statuses/lookup in batches of up to 100).