Note non-existing times mostly happen when you go from winter time to summer time. You set the clock ahead an hour at let's say 2:00 in the morning. So you go directly from 2:00 to 3:00. 2:30 does not exist.
So let's say that you plan a meeting at 2:30 in the morning in a country that does not use DST. Then they decide to use DST and set the clocks forward one hour at 2:00. Your meeting was supposed to take place at 2:30 local time, but that time no longer exists! As I see it, the right thing to do is to alert the user of the problem.
# Zone NAME GMTOFF RULES FORMAT [UNTIL]
Zone America/New_York -4:56:02 - LMT 1883 Nov 18 12:03:58
-5:00 US E%sT 1920
-5:00 NYC E%sT 1942
-5:00 US E%sT 1946
-5:00 NYC E%sT 1967
-5:00 US E%sTYou store the timestamp, and a foreign key to the timezone as it was defined at the time the timestamp was inserted (orginal revision). You then schedule a sweep (every day, say) that simple detects which timezones have received an actual update, then select/update any rows which were created with the previous timezone entry. Not very difficult to implement, and generates the minimal amount of overhead possible.
The only exception is the one raised by laut regarding an event scheduled for say 02:30, and where 02:30 simply does not exist after a rules update. The sweep can detect these and in theory should alert the user to the inconsistency. An annoying edge case to be sure. :/
This would be necessary not only for the example provided in the link, but also for larger changes, like several years ago when the US extended DST hours, and several other countries followed suit. (i.e. DST now begins on the second Sunday of March, rather than later in April)
Then when a new set of rules is detected (perhaps notification of updates at the OS level should be turned into a standardized publish-subscribe API to avoid too many applications polling for changes all the time, especially wasteful on battery-powered devices), move the current version to the previous version, scan for timezone rule differences, then scan your collection of records that use those timezones, parse them down to only those records affected by the new rules, and finally apply corrections to those records affected by the new rules.
Extending further, if this approach works, perhaps an OS-level, perhaps git-backed storage of versions of timezone rules could avoid duplication of effort. Combined with a publish-subscribe service, it can auto-prune itself based upon the list of subscribed applications and when the oldest subscriber last hit the version store.