Depends on terms of contract and contracts can be changed at any time.... so yes its legal.
Q. Isn't this illegal? I mean, he's basically forcing a monopoly and
killing anyone that enters the market?
A: Depends on the scale and laws in your country. A local advertising contract that prohibits certain actions is hardly a monopoly and your have a hard time getting a small claims court to hear your case and that's even if both parties agree to it.. (UK).
Q. Can he legally deny people being listed on their site on these
Do people not have the right to advertise everywhere?
A: Yes, its called a terms of contract.... and contracts can always be rewritten. If the customers doesn't like their terms then they are welcome to go elsewhere - your customers are not being forced to use their service.
Q: How do I proceed to deal with such a matter, or is it a lost
A: Your competitor is obviously doing something better, or has better exposure otherwise your customers would tell your competitor to stick it. (not that I agree with their terms but if they are getting a percentage of sale then obviously they don't want other advertisers having the same chance and I understand their reasoning).
Back to the drawing board
It sounds like your website is not offering anything that the customer can't get else where and one of the reasons they are flocking to the other site, in order to beat the other site you need to out smart them. Time to rethink your strat, reduce fees, revert to a different pricing model etc.
The first approach should be getting more traffic than your competitor and not focusing on how much money you can make or how many cars you list. The more traffic you get the better proof your have to why customers should choose you, 'Because your site gains more exposure, more hits, and faster sales'. But this isn't my niche but a little common sense says this ;)
I understand your frustration but sounds like typical business ;)