You're not required to pay him, obviously, but that doesn't mean you're "free". A lot of companies will only pay a referral or fee if a recruiter brings them new people they don't know about. So those 60 companies who received your resume may have already filled the position it was sent in for, but they still entered your information into their database and keep your resume on file. So if/when you start working with a legitimate recruiter, they may not get paid as much or not at all. And obviously once the recruiter realizes that they may not push hard to get you the job, or even steer you towards other companies that will pay full price.
I had a somewhat similar situation happen. A company I wanted to work for had a place on their website to apply for jobs, and I found one I was interested in and applied for. I never heard from them. A friend of mine who worked there eventually asked me about another opening, and they had a referral program where he'd get a few $k. After he talked to HR they said he'd get no referral since I was already in their system. I told him to ask why they never contacted me and he said their response was "Oh, we pretty much never look at applications submitted online".
It didn't strike me at the time as to how shady that conduct was until later. Fortunately I went somewhere else anyway.