My personal opinion is that the best method to generate unique primary keys (PK) is to autoincrement last used PK value. It is so called surrogate PK. If you have more questions, please ask.

how does the "autoincrement" get implemented?

I can imagine something like Select max(PK) from table, since PK field is indexed anyway, but this is a nightmare waiting to happen in a multi-user environment.

I thought about the keys table being the storage point for the "next" key - but that's also extra overhead/complexity

I'm working on a modification of the HighLow key strategy:
http://fox.wikis.com/wc.dll?Wiki~HighLowKeyGeneration