O que você precisa é de uma sequência gerada externamente e vinculá-la às suas 2 tabelas
Você deve ver o que o flickr fez, veja este link:http://code.flickr.com/blog/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
Você cria a tabela que gera o id:
CREATE TABLE `Tickets64` (
`id` bigint(20) unsigned NOT NULL auto_increment,
`stub` char(1) NOT NULL default '',
PRIMARY KEY (`id`),
UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM
e para obter o novo id você faz assim:
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
O Twitter também fez recentemente algo chamado floco de neve, você deve procurar no repositório do github
Mas principalmente veja o que o flickr fez, é mais simples e pode ser manuseado facilmente
