Sounds like you have, er, "legacy data" in your database. Happens all the time, e.g. when applications that assumed an 8-bit encoding for text suddenly need to become Unicode aware. Typically you need to migrate that data, and often but not always that means some downtime.

The most important thing in these cases is to know which records are in which state: ideally they should all be in the same state, then you update it in an atomic process. Usually this is a pain , but if you can't easily tell which data is in what state, it's a much greater pain :/