Thanks for all the helpful answers! To summarize, there are 6 ways to tackle my issue:

1. recycle deleted record
2. pack after delete
3. replace primary key value of deleted record
4. add filter to primary index
5. change primary index to regular index
6. use surrogate key as primary index field

In my particular case, i probably will go for #3 for now, and i think i will see if i could use a surrogate primary key next time around.

Thanks again all!