CultureInfo and RegionInfo data represents a cultural, regional, admin or user preference for cultural settings. Applications should NOT make any assumptions that rely on this data being stable. The only exception (this is a rule, so of course there's an exception) is for CultureInfo.InvariantCulture. CultureInfo.InvariantCulture is supposed to remain stable, even between versions.
There are many reasons that cultural data can change. With Whidbey and Custom Cultures the list gets a little longer.
So if you format a string with a particular date/time format, and then try to Parse it later, parse might fail if the version changed, if the machine changed, if the framework version changed (newer data), or if a custom culture was changed. If you need to persist data in a reliable format, choose a binary method, provide your own format or use the InvariantCulture.
Even without changing data, remembering to use Invariant is still a good idea. If you have different . and , syntax for something like 1,000.29, then Parsing can get confused if a client was expecting 1.000,29. I've seen this problem with applications that didn't realize that a user's culture would be different than the developer's culture. Using Invariant or another technique solves this kind of problem.
Of course you can't have both "correct" display for the current user and perfect round tripping if the culture data changes. So generally I'd recommend persisting data using InvariantCulture or another immutable format, and always using the appropriate formatting APIs for display. Your application will have its own requirements, so consider them carefully.
Note that for collation (sort order/comparisons), even Invariant behavior can change. You'll need to use the Sort Versioning to get around that if you require consistently stable sort orders.