Answer #1: this depends on which DBMS you use: Some databases, such as PostgreSQL, Oracle, etc... allow for primary key re-use, simply by restarting the cycle once the top integer is reached. It will restart the cycle looking for the lowest possible free value, and start moving upwards through the available values.
Answer #2:
There is a lot of discussion in database design theory about what types of primary keys are best for different situations. My approach, before seriously reading some of this, was to simply stick an auto_increment field everywhere, thinking this was the most efficient use of the database resources, rather than maintaining my own primary key. I now think differently.
The main thrust of these discussions center around the question "when do you use a natural key, and when do you need an artificial key?". An artificial key is one that doesn't directly relate to the data itself, such as an auto_increment field. The auto_increment field is meaningless beyond its job as a provider of unique integers. However, there are many times when the nature of the data itself means that you don't need an auto_increment field at all, because somewhere in that table you have other unique values. Why muddy your data model by requiring artificial unique values when you have a unique field such as "username", or "SS_number" for example. The very nature of a username in a system requires it to be unique. The very nature of a social security number requires it to be unique. Thus you achieve your unique values, and hey there's a plus: these values are actually meaningful in other ways as you manipulate the data. This can actually make certain types of queries much more readable.
So the question to ask yourself is: "is there any attribute of a classified ad record that is already unique?". If so, then that is probably your best choice for a primary key. For example, is there an invoice number generated for each classified ad?
Answer #3:
You can definitely manage your own primary key, using whatever algorithm you want, as long as you use efficient methods of checking for uniqueness (keep your re-tries low). But, whatever you do, don't start "periodically compacting the keys to reclaim pockets". A primary key is your main data integrity mechanism. Once set for a certain record, it should be left alone. Once you start reshuffling keys, you will have to make sure that you change any other tables with records referring to those keys, and you will end up with one big headache.