Master-Master auto-increment ID problem

[Nicolas Jauffret]

Hello,

we have a master-master configuration using version 5.0.27-standard-log.
We use even numbers for key id inserts on the first server, and odd 
numbers on the second.

Our issue : about once a week, on replication, we get the following error:

080807 11:38:10 [ERROR] Slave: Error 'Duplicate entry '2108084' for key 
1' on query. Default database: 'our_database'. Query: 'INSERT INTO 
`our_database`.`our_table`(`field2`,`field3`,`field4`) 
VALUES('2','3','4')', Error_code: 1062

(Theses errors does not depend on one table or another, it occured from 
time to time with different inserts on different tables)
In these inserts, the value of the key field is not specified so mysql 
shall use an auto-incremented id.
But, as a matter of fact, in these cases, the key id it generates is 
already used.
And when we take a look at the already existing row, all data in it is 
NULL, or in default values...

Would you know what it can come from ?

Regards,

Nicolas Jauffret