駐車場契約の解約されたか判らないが、違う車がいつの間にか停まっていた。前契約者は何も出来ないのですか

駐車場は居住権ではないから貸し主側の意向で法的にも、自由に解約可能みたいですが

何らかの理由で賃料未払生じて、貸し主側から解約通知も電話もなく

ある日から突然
借りていた場所に違う車が停めてあり、契約締結されていても

前の契約者は法的に引き下がるしかないのでしょうか

支払方法がどのようになっていたのか分かりませんが、あなたが遅れなく支払っていたにもかかわらず、実は未払いが生じており、これまでに一切連絡がなかったというようなケースは考えにくいです。
違う車が停まっていた時点で貸主に連絡はしていないのでしょうか?

事実連絡なく、問い合わせても払ってないから別の車を契約して置かせてると答えました

支払いがされていなかったというようなことはないですよね?

だから払いそびれが間空けて数ヶ月

聞き方が悪かったですね。
相手側で確認ができていないというだけで、あなたは遅れなく確実に支払いをしているのですよね?