I remain unconvinced that there is any reason to do anything regarding random values in this Autonumber primary key.
First, the assumption that the change happened "by magic" seems to underlie a lot of the thinking about that. I doubt that for two reasons.
- It's one of two options. The change could have happened when anyone at some point in the past wondered what would happen, or when someone, at some point in the past inadvertently changed it. Belatedly that person learned there was no going back.... One thing for sure is that some other change didn't "just happen". Corruption doesn't magically result in a valid implementation that has functioned for some unknown period of time.
And that brings up the second point. It's been in this alternate state for a while with no one reporting problems with data.
I recently started working on a database that i believe no one has touched for several years.
That alone should give pause to any plan to "do something about it". If it ain't broke, don't fix it. Of course, I'm assuming here that, by "no one has touched", the OP means no developer had modified it for several years, although users have been using it in their day-to-day work. That implication is strong through the rest of the thread regarding multiple tables with the random values.
And third, if this difference only came to light when the OP was tasked with "working on a database", then the strong implication again is that no user has ever noticed or cared that the Autonumbers are random, not incrementing.
In summary, the use of random vs incremental values in and of itself is a benign choice. The fact that 99.9% of the time we see incrementing values in Autonumbers doesn't invalidate the remaining 0.1% of the times when random values are used. Change it if you have the time and money (i.e. the value of your salary) to invest and are willing to do that. If you have to explain to someone that you devoted some percentage of your budget to making a change that produced no value to the project, maybe that's not a good plan.