Mark,
The routine I use is as fast as Autonumber--remember, just because you don't 'see' a table in Access for Autonumber and you don't 'see' a routine--it's still there. Access has an internal table, and it must read from disk, lock, and write to disk. No getting around that, period.
As far as which table to use the routine on--I still use Autonumber when I need a quick & dirty unique number for some lookup table or something. But if that number is, say, a Customer ID or Order ID, then I never do. This due to not only non-specific glitches such as your case, but also the fact that compacting, importing/exporting, copy/pasting/appending/deleting, etc, etc. all can cause the autonumber to change or get resequenced.
Maybe I don't understand your problem fully. Do you just need to re-sequence? If so, why wouldn't deleting the Autonumber field and recreating it work? If that answer to that is that the Autonumber field is being used in a Relationship of any kind and that related records will now be orphaned--then it is even more critical that you not use autonumber. Also, I'm not sure about Access Xp, but I think the newer Access versions might have more control over increment stepping, maximum value, etc, so one of those options might be at play in your problem.
Also, when does this jumping back occur? Is there an event or something that triggers it?
Again--I know it's more work, but I wrote the routine once years ago and I just copy it into every Access project where I need it and it's little overhead.
--JIm