finding reusable ids

I have a table that creates "check-out" records that stores information when
a particular resource is being utilized. I want to maintain a friendly
shortened ID so people can reference these check outs.

At any given time, there should not be more than 999999 or so check-outs, so
as the check-outs get checked in, the old IDs would become available. What
is the best method to query for these resusable IDs that would not be
assigned to checked out items? It seems that it would be quite inefficient
to look at the entire table to see which ids exist, then increment
accordingly. For some reason, I feel that there would be something already
available to solve this.

example set:

uid co-id checked-in?
1 1 n
2 2 n
3 3 y
4 4 n
5 3 n

obviously, this is a small sample set, but the id 3 can be reused, so I'd
like to reuse it without using a external tracking mechansm. My table has
1,000,000+ records.

Kenji