Если верить документации, такое может быть, если вызывать mysql_insert_id после запроса, не генерирующего AUTO_INCREMENTное значение.
Смотри внимательно - у тебя всегда mysql_insert_id() вызывается только после запросов INSERT и всегда эти запросы работают с таблицей, имеющей AUTO_INCREMENTное поле?