You don't necessarily need to support two formats; you need to support redirecting the previously-issued URLs. This _can_ be accomplished by supporting the old format, but it doesn't _need_ to be.

Instead, you could just use a database of redirects which you append to when you make format changes. For some applications, the overhead of maintaining a redirect service is far lower than trying to maintain support for multiple formats. (And this redirect service may even be something you need/want for other reasons.)