If I were to be awarded a utility patent, certificate in the mail and all, and it was later discovered by me or someone else that prior art existed before the time of the initial patent application submission, what impact would that have on the enforceability and indeed even the validity of that patent?
To successfully sue for patent infringement, you need to hold a valid patent. An issued patent is not irrefutable proof that you have a valid patent; patents are presumed valid, but the defendant can raise invalidity as a defense in an infringement suit. One of the conditions for a patent is that the invention is novel (details vary depending on filing date). Even if the USPTO doesn't think there was prior art, that doesn't mean the defendant can't try to convince the court there was prior art. If the defendant proves that the invention was not novel (or any other reason the patent is invalid), the defendant wins the infringement suit.
There are a couple ways to challenge the patent for lack of novelty, which can lead to a challenge before the USPTO or before a federal court. If it's challenged before the PTO and found invalid, the holder loses the patent. If it's challenged in a lawsuit and the holder loses, they can never again assert that the patent is valid in any US court (except when appealing that decision or in a few other special cases). So if it's challenged in court and the challenger wins, the patent is also effectively invalid.
Until someone raises the existence of the prior art, your patent is still presumptively valid.
If someone discovers it, they could either (1) go to the PTO to try to have it cancel your patent, (2) the prior art could be raised as a defense in a suit to enforce the patent in federal district court, or (3) they could probably bring a declaratory judgment action in federal district court to have it declared invalid.
But, you might be sanctioned if the court determined that you filed suit knowing that there was prior art that could defeat it, and you would probably be required to disclose the information about the prior art and when you acquired it in the course of disclosures or discovery in the patent enforcement lawsuit.
Of course, if there was a rare default judgment in an enforcement suit or counsel for the defense didn't raise prior art (e.g. simply arguing that their invention isn't the same as your invention), the issue would be waived and presumptive validity would be enough to get you over the hump.
If you hired someone to look for prior art and they missed it, you might have a suit against them for negligence for the amounts you expended after the search came up clean to get the patent including their fees, although this would depend upon the agreement with the search firm and upon how obvious that prior art should have been to find. Anything that made it past a PTO patent examiner couldn't have been that easy to find.
The patent would be challengeable and would likely be ruled invalid.