You just proved to the company that your conduct was above board. Not so for the recruiter, who is going to have to sort it out with the company. Let's see what happens next. Chances are pretty good that the company will stick to its policy of not offering relocation packages and it can justifiably argue that it cannot be bound to a representation by a third party, a representation that the third party conjured out of its lively imagination. Most likely, your relocation package is going to come out of the recruiter's pocket. Don't feel sorry for him.
The recruiter could refuse to pay up. But then, he has to weigh the con of losing the company as a client, the possibility of getting fired by his management for losing the company as a client - unless the recruiter owns the recruiting firm, that is - and the con of parting with the money to pay for your relocation package. No pressure :)
Of course, you are no fool, you are not going to take his word that he is going to pay you the relocation package AFTER he gets the money from the company. Right? :) Insist on "Show me the money". Up front.
Post-note from user19170: "So the company got back to me and said they did not think I was being unprofessional. That is a relief. Secondly, they are paying my relocation costs. Sadly, I do not know what happens to the recruiter, but a good guess he is no longer associated with my new employer."
OK, the recruiter had a bad day at the office - he'll live :) There are plenty of other parts in the world where he would have lost a few body parts if not his life for his stunt. And hopefully, going forward, he learns to curb his enthusiasm for making up stories.
Back to the important stuff: you've got (1) the offer and (2) the relocation package. Well done :)