Jon,
I don't know if this will help you or not, but this is what I do. When I have a table with important information in it, I add an 'Archive' column which is a TINYINT.
Instead of deleting something, I set it's Archive value from 0 to 1. This way, I can "delete" without worrying about autoincrementing problems.
Show archived items:
SELECT * FROM TABLE WHERE ARCHIVED = 1
Show non archived items:
SELECT * FROM TABLE WHERE ARCHIVED = 0
Maybe this helps...
Joseph