No, alas - the Twitter terms of service are very clear. If you are storing a tweet, when someone deletes that tweet you have to delete all of your copies of it. Full stop.
The only way I can think of is for Twitter to publish different deleted tweets to different API keys and then see which one the web site surfaces. Not very hard but not trivial either.
problem solved.
Do the TOS require you to only store them in mutable data storage?