What you are doing is a bad idea.
AUTO_INCREMENT is really just meant for key association (which is why it must be primary to auto_inc in the first place)
It's not intended to be a userID or something for you to rely on.
It's just a unique index.
And once the associated value dissapears, it's gone forever.
Personally...
I wouldn't do it this way at all though.
I'd just do a LIMIT CLAUSE
say "SELECT * FROM myTable LIMIT $offset,1"
where offset is the last viewed record starting at one.
If you are dead set on doing it your current way, then you should switch your table type to innoDB rather than myISAM which is the MySQL default. Of course, you'll need MySQL 4 for innoDB, so get ready to upgrade if you haven't done so all ready.