I use e-classifieds by Hagen Software, http://www.e-classifieds.net/
as does one of my customers, who recently upgraded his version. They're pretty good. You have to get one of the paid versions for some of the features you're looking for, and they are reasonably priced at the low end.
You can probably find most any feature you want. It's just a question of which version of the program has them (as well as the price you're willing to pay).
You can hack the scripts and make your own changes, necessary if you want to have categories other than the ones they include, or if you wish to change some of the options in the existing categories.
You can upgrade at any time by paying the difference in price between versions. Be aware, though, that not all versions are compatible with each other. There are about 3 levels. You can upgrade to programs on the same level, but may either need a special script to go up a level, or can't upgrade at all and retain any existing ads. Unfortunately, this applies as well to the free version they have.
Even so, when I took a look at all the classified programs I found near the beginning of last year, they were the best of class. They probably still are. I've taken just a quick look at some new ones recently (including PHP ones) and was not impressed.
If you decide to buy a license to one of their scripts, I hope you'll let me know first. I don't get anything for recommendations, but I've made several suggestions to Phil (Hagen, the owner) and he might take them more seriously if he's aware of customers that I recommended the program to. Hopefully, he's improved the installation instructions since my suggestion on that point. There were a few steps missing that he assumed people would know to do, so the program would not work if the instructions were taken literally and figured to be complete as is.
My customer, Matt, did okay on his installation (I only had to help him with permissions), so the instructions are probably better now.