Having worked with a variety of headhunters, and interviewed at companies that work with a lot of headhunters, the companies do not expect the head hunters to be honest, but they certainly expect you to be. the first thing I do at the beginning of every interview I go on is give them a copy of my resume I know is correct and basically say "I don't know what the headhunter gave you, but here's a correct copy."
Also, you can work with more than one head hunter at a time; there's no reason to work with only one. If the lying one keeps getting you good interviews, then ask him not to "fix" your resume, but I wouldn't worry about it too much.
That being said, there are plenty of headhunters that do what I call "marking their territory." A lot of companies maintain a database of potential candidates and their resumes. If and when you get a position, they pay the headhunter who found you, but oftentimes they will pay whoever put you into the system first. So, headhunters will scour job boards and tell you about wonderful positions they've found and how they have a really good relationship with the hiring manager (who they don't know) and ask you if you're OK with them talking to company. When you agree, they simply submit your resume to the companies candidate database. Other recruiters will know this and will therefore have no incentive to work with you. If you are in need of a job or you might have liked it anyway, everyone wins, but most of the time it's just a way to squeeze their competition and it can really screw you because plenty of companies won't "expire" the candidate entry for a year or two. When you need a job down the road a little, recruiters won't work with you because someone else has basically excluded you (for their purposes) from a number of good places.
If you suspect your headhunter may be doing this, then tell them sternly that you do not permit them to submit your resume anymore ANYWHERE.