The utility company almost always has a statutory right to acquire and condemn easements for telephone lines and very likely had a right to do so when they were put up.
Even if it didn't have a valid unrecorded easement, it is likely in the circumstances that you describe that is has a "prescriptive easement" which arises when property is trespassed upon openly for a sufficient time period, or one of several other kinds of implied easements such as an easement by estoppel (which arises when a structure is built on property with the implied permission of the property owner who does not make a timely objection and the person building the structure relies upon that permission to their detriment in a way that it would be unjust to allow the property owner to revoke that permission later on).
When you buy real property you are bound not just by easements of record, but also by easements whose existence would have been apparent upon a physical inspection of the property. Often there is also an express exclusion from title insurance for unrecorded utility easements in the fine print of a title policy.
A telephone pole on the property is an easement whose existence would have been apparent upon a physical inspection of the property, so you are bound by this easement if it existed when you purchased the property, even if there was no recorded document noting that it existed.
You should contact Verizon to determine whether they would be willing to vacate their utility easement that blocks your old driveway, and if so, on what terms they would be willing to do so (often they would be willing to take down an obsolete telephone pole, but only at your expense).
If a new survey of the physical property was done and did not note the physical pole on the property, you may also have a claim against the surveyor for the cost of remedying the problem that his survey should have revealed (although there may be contractual limitations of liability either at all, or in the amount of damages allowed if there is liability). But, often only an "improvement location certificate" to show that the main structure on the property is within the boundary lines is done, and then noting the telephone pole would have been beyond the scope of the surveyor's engagement.