Autoincrement в MySQL

>Суть следующая, есть поле autoincrement, нумерация идёт по порядку,

autoincrement это не для нумерации. оно надо чтобы у каждой записи был уникальный id.

>после удаления записей в середине, порядок нарушаеться,

кокой порядок? у тебя веть нет порядка.

сделай еще одно поле. и пиши в нево например unix time stamp + милисекунды. при выборке сортируй по этому полю. и будет тибе порядок :)