My questions are, where does this put me legally and what are my
options? . . . Also, if I want to keep the tenants, how should I
proceed? And if I don't want to keep them, do I have that option?
Your Rights With Respect To The Tenants
If the agency is telling the truth and the agreement made with the agent was for four tenants but their records and document only listed three by accident, you probably can't insist on additional rent or evicting the fourth tenant because if your agent does something on your behalf, that is binding on you just as much as if you had signed them up personally in that manner. This is true even if the agent didn't actually have the authority to rent the place to four people based upon your communications with the agent, because the agent has "apparent authority" to bind you in your agent's dealings with the prospective tenants.
You probably have the right to insist that the fourth tenant sign the lease to conform to the actual agreement that was reached (four tenants in exchange for the rent stated in the lease). If the fourth tenant refuses to do so, that would be a repudiation of the lease/contract and would prevent him from claiming that he is a valid tenant of the property pursuant to the agreement reached with landlord through his agent. If the fourth tenant refused to sign, you could therefore insist that the fourth tenant pay additional rent or be evicted if you wanted to.
On the other hand, if the agent is not accurately relating the facts, and there was never any agreement to have more than three tenants (as your communications with them and the written lease suggest), then you would have the right to evict the fourth tenant or insist on additional rent from that tenant. But, it might be hard to prove that the agent is not being accurate because it sounds like the agent and the tenants will testify consistently with each other and there were probably no other witnesses to the discussions between them.
The Fourth Tenant Might Have Liability Anyway
Also, at common law, you could sue the fourth person for unpaid rent during the period that the tenant was actually there anyway, since the fourth tenant was in "privity of estate" with you. (If someone actually signs the lease then they are in "privity of contract" with you.)
England abolished the doctrine of privity of estate in most circumstances for residential tenancies in 1995. But, it is possible that this fact pattern is one of the situations in which the privity of estate doctrine remains in force since the 1995 reforms largely apply to assignments of leases by people who are tenants on the original lease, rather than occupants of a rented property who never signed a lease and never received a formal assignment. I don't have the legal research tools to confirm that accurately. But, none of the U.K. Landlord and Tenant Acts currently in force that I could locate addressed that issue, so the common law rule may still apply in this situation.
If the doctrine of privity of estate does allow a suit against the fourth tenant based on occupancy without signing a lease, the incentive to even try to get the fourth tenant to sign a lease is very small indeed - you get no benefit at all from it other than slightly easier proof in an unpaid rent collection lawsuit if the agent's story is believed. If it doesn't the considerations earlier in this answer still apply.
Practical Considerations
All of this being said, there is also a practical consideration to consider. It you try to kick out the fourth tenant or impose additional rent on the fourth tenant, if the fourth tenant refuses to sign the lease, or if you believe that the original agreement did not include the fourth tenant, you still have to weigh the pros and cons of bringing an eviction or unpaid rent lawsuit.
The lawsuit will cost you money (requiring you to advance money even if you are awarded attorneys' fees which may be impossible to collect from the tenants). You won't get your attorneys' fees for the lawsuit if you lose and will also have to pay their attorneys' fees if you lose. Tenants whom you are suing are unlikely to be cooperative on any other matter upon which you want their cooperation, and may bad mouth you, for example, in online consumer reviews. Unlike a typical eviction where the rent is not paid, it is very likely that the eviction will be contested, and if it is, the court could order the fourth tenant to sign the lease, but provide you with no other remedy if the court believes the story put forward by the tenant and the agent.
If you don't sue, you won't incur attorneys' fees, you can still evict everyone if the rent isn't paid, you can still try to collect unpaid rent from three other people, and you are much less likely to have a dispute with or non-cooperation from the tenants. The only benefit you get from having a fourth person on the lease if that was the original deal (or if you can't prove that it wasn't the original deal) is that you have one more person you can sue for back rent if the rent isn't paid.
If I decide to break my agreement with the agency, do I have grounds
to do that?
Terminating The Agent
Often you can terminate an agreement with an agency without cause. If the agency agreement says that you can, you are free to do so and probably should because at a minimum they are sloppy and poor communicators.
Generally speaking, even if you can't terminate the agreement without cause, you can terminate the agreement for cause, and the contradiction between their prior communications with you and their current communications with you probably constitute good cause to terminate the agreement both if they are telling the truth not, and if they are not accurately recounting the facts now.
But, to be clear, terminating the agent won't affect the rights of the tenant.
Suing The Agent
If you clearly do lose money because the three tenants on the lease don't pay rent and for example, you get a judgment against them which can't be collected due to bankruptcy or them moving abroad to a place where it is not economical to collect a money judgment from them, or just not having any assets or income (or some combination thereof), and it turns out that the law does not allow you to sue the fourth tenant, and the fourth tenant was not judgment proof, you would probably have a right to sue the agent for the lost rent caused by the agent's negligence in failing to get all four tenants to sign the lease.
But, the cost of proving that in a typical case would not be worth the money since this would be much harder to prove than simply proving that someone signed a lease agreeing to pay rent and didn't pay rent as agreed. If the agent didn't agree to pay for your losses voluntarily it might not be worth the time, trouble and risk of not prevailing in that lawsuit to pursue, even if you could get attorneys' fees for your suit against the agent if you won (which you probably could in England). The risks of doing that include paying the agent's attorneys' fees is you lose.