Hey Simon
I've done this on a VERY small scale (i.e. just for me, with Admin rights, and just in a non-Prod environment). I can't claim that it will work in Production, on any kind of scale, with standard PM users.
You can add some VBA magic into the Clarity_SavePrecheck procedure (which lives within the CA_IntegrationHooks code module, in the Global.mpt file), which cycles through each task. Where are task doesn't have an ID, it makes a webservice call to PPM to run the query to get the next auto-number ID, and puts the ID into the Task ID field.
Again, it's hacky and I've never tried it in a Prod environment. Test, test, test!
Also, to roll it out you'll need to get friendly with your MOE team to push an update out to every user's Global.mpt file.
Cheers, and good luck!
Alistair