I do as rgbean suggests on my tables that encounter a lot of traffic (excessive additions and deletions). I add an index named deleted with a tag of deleted() in descending order. When I need to add a new record I simply apply the deleted index, go top, store the record number to a variable, gather the new information, undelete the record, and apply the previously active index. This process has worked very well for a long time for me without incident.
For the less active tables I have a reindex function which steps through each table packing and reindexing them.
I hope that helps!