We use two fields for each primary key: an auto incrementer and
a 'database id' field.

That of course means in our code we often have to set the db id field
whenever we insert a record, and use it when doing joins etc. However
I wouldn't want to retro-fit it into a large application.