Aquí está la respuesta, según lo sugerido por Alexandre:
cuando usa id=LAST_INSERT_ID(id), establece el valor de mysql_insert_id =el ID actualizado, por lo que su código final debería verse así:
<?
$query = mysql_query("
INSERT INTO table (column1, column2, column3)
VALUES (value1, value2, value3)
ON DUPLICATE KEY UPDATE
column1 = value1,
column2 = value2,
column3 = value3,
id=LAST_INSERT_ID(id)
");
$my_id = mysql_insert_id();
Esto devolverá el valor correcto para $my_id independientemente de la actualización o la inserción.