MySQL auto increment problem with deleting rows / archive table
You can check the AUTO_INCREMENT value from INFORMATION_SCHEMA like this:

SELECT AUTO_INCREMENT FROM information_schema.tables
WHERE table_schema='mydb' AND table_name='x';


you should also see the AUTO_INCREMENT with

SHOW CREATE TABLE mydb.x\G


SUGGESTION

If the table has barely 1000 rows, you could manually compress it and force to have MAX(id) each time. Suppose the table looks something like this:

USE mydb
CREATE TABLE x
(
    id INT NOT NULL AUTO_INCREMENT,
    ...
    PRIMARY KEY (id)
);


Try doing OPTIMIZE TABLE manually as follows:

InnoDB or MyISAM tables with no non-unique keys

USE mydb
CREATE TABLE x_new LIKE x;
INSERT INTO x_new SELECT * FROM x ORDER BY id;
ALTER TABLE x RENAME x_old;
ALTER TABLE x_new RENAME x;
DROP TABLE x_old;


MyISAM tables with non-unique keys

USE mydb
CREATE TABLE x_new LIKE x;
ALTER TABLE x_new DISABLE KEYS;
INSERT INTO x_new SELECT * FROM x ORDER BY id;
ALTER TABLE x_new ENABLE KEYS;
ALTER TABLE x RENAME x_old;
ALTER TABLE x_new RENAME x;
DROP TABLE x_old;


This should preserve all id's and assign AUTO_INCREMENT appropriately.

It should work just fine with MySQL Replication. 

CAVEAT

If the ids are different for any reason between Master and Slave, blame MySQL (I mean blame Oracle) : http://dev.mysql.com/doc/refman/5.5/en/replication-features-auto-increment.html

If the aforementioned suggestion does not rectify this, there is only one thing left to do and it is guaranteed to work. What is it?

Run this on the Master Only:

mysqldump -uroot -p... --triggers mydb x &gt; mydb_x.sql
mysql -uroot -p... -Dmydb &lt; mydb_x.sql


With a table of 1000 rows, this should 


go pretty quickly
replicate and produce an exact copy on the slave
restore auto_increment behavior to Master and Slave


Give it a Try !!!

UPDATE 2013-02-11 19:30 EDT

Let's assume that x and xhistory have identical layouts. Let's also add some columns:

CREATE TABLE x
(
    xid int(10) unsigned NOT NULL AUTO_INCREMENT,
    col1 ... ,
    col2 ... ,
    col3 ... ,
    PRIMARY KEY (xid)
) ENGINE=MyISAM AUTO_INCREMENT=124 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

CREATE TABLE xhistory
(
    xid int(10) unsigned NOT NULL DEFAULT '0',
    col1 ... ,
    col2 ... ,
    col3 ... ,
    PRIMARY KEY (xid)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;


Perhaps you could just use the REPLACE command. It mechanically operates as either an INSERT or UPDATE via DELETE and INSERT.

REPLACE INTO xhistory SELECT * FROM x;
TRUNCATE TABLE x;


Previously existing rows get deleted from xhistory and then inserted from x into xhistory. New rows are simply inserted.