The AUTO_INCREMENT column always increases. However, you can specify an AUTO_INCREMENT column as secondary column in a multiple-column index to "divide" the AUTO_INCREMENT into several groups.
Example:
NOTE THAT id2 IS THE AUTO_INCREMENT COLUMN here, and not id!
CREATE TABLE `testAI` (
`id` int(11) NOT NULL default '0',
`id2` int(11) NOT NULL auto_increment,
PRIMARY KEY (`id`,`id2`)
);
mysql> INSERT INTO testAI(id) VALUES(1),(1),(2),(2),(3),(1);
Query OK, 6 rows affected (0.00 sec)
Records: 6 Duplicates: 0 Warnings: 0
mysql> SELECT * FROM testAI;
+----+-----+
| id | id2 |
+----+-----+
| 1 | 1 |
| 1 | 2 |
| 1 | 3 |
| 2 | 1 |
| 2 | 2 |
| 3 | 1 |
+----+-----+
6 rows in set (0.00 sec)
There are now three groups of auto_increment values.
mysql> DELETE FROM testAI WHERE id2>1;
Query OK, 3 rows affected (0.00 sec)
mysql> SELECT * FROM testAI;
+----+-----+
| id | id2 |
+----+-----+
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
+----+-----+
3 rows in set (0.00 sec)
Still normal.
mysql> INSERT INTO testAI(id) VALUES(1),(1),(2);
Query OK, 3 rows affected (0.00 sec)
Records: 3 Duplicates: 0 Warnings: 0
mysql> SELECT * FROM testAI;
+----+-----+
| id | id2 |
+----+-----+
| 1 | 1 |
| 1 | 2 |
| 1 | 3 |
| 2 | 1 |
| 2 | 2 |
| 3 | 1 |
+----+-----+
6 rows in set (0.00 sec)
There, that's how you want it!

Maybe you can reorganize your data in some way (insert a dummy BOOL column maybe?) so that you can use this method.