Professors are busy people. This person's failure to make good on the promise of a letter could be due to a variety of reasons, being a "jerk" being only one of several possibilities. It could be just forgetfulness, or perhaps they wrote the letters but didn't include the correct postage, or the mail got stolen from the mailbox where they dropped off the letters. Things happen, and sometimes we are too quick to find fault. Being absent-minded is not an excuse, but lack of malicious intent definitely impacts the validity of accusations.
Therefore, I would tread lightly and first ascertain the reason. If you really need closure on this, the best way is to NOT talk to the associate dean, but to discuss this with the professor privately, and very VERY politely. Do your absolute best NOT to come across as being accusatory, pursue not the person but the objective facts -- as a student in this department, you are in a much more vulnerable position than tenured faculty, and should account for this in your decisions and actions.
Drop by during this professor's office hours, sit down calmly, and in a polite, humble tone simply explain what has happened years ago.
Do not say "but you never mailed those letters". This immediately puts the person on the defensive and the conversation will quickly devolve from constructive feedback to denial and conflict. This will have zero benefit for you, but can have negative consequences down the road in ways that are difficult to anticipate right now.
Instead, one approach is to say: "It appears that the letters from one of my references were not received by the institutions to which I applied, and I am trying to figure out if this was through a fault of mine, perhaps lack of clear communication on my part about what I was requesting. I feel uncomfortable talking about this, but I just wanted to see if you had any recollection of that situation and whether you recall any challenges with providing those letters. This will be very helpful to me in understanding how to improve the way I solicit recommendation letters for future fellowship or employment applications."
This interaction presents a great opportunity to learn whether you did, in fact, do something that may have contributed to the unfortunate outcome of receiving no letters from this person. Was it a miscommunication about the application timeline, addresses where to mail the letter, or something else? Chances are you will have to solicit letters again in the future, and knowing what caused the malfunction in the process back then can help you prevent the same issue from happening in the future. What a great opportunity to learn from the past and improve future results.
As @EnergyNumbers noted, "When you ask someone for a letter of reference, and they agree, it's up to you to do what you can to ensure that they write it and submit it." I absolutely agree. You needed those letters, not the professors. Therefore, it was your responsibility to follow up and confirm whether they had mailed the letters you requested. That's just how this stuff works. For this reason, if anyone should be blamed for what happened, it's not the professor. For this reason, I would disagree with @Anonymous Mathematician's position that "It's too late to fix your applications, but you deserve an apology." I would agree that you might deserve (I would say, not deserve, but "benefit from") a brief explanation of what happened. But whether to apologize for this or not remains to be seen, and should be up to this professor to decide. It's their conscience, let them find the course of action that they find acceptable. If this is at odds with your notion of fairness and justice, well, the world does not have to operate in accordance with your notions. Everyone has different ideas of what they deserve, and sometimes letting go and adjusting one's expectations is a much wiser strategy than pushing to get what one believes is their fair share, or fishing for apologies. Letting go is not easy, and absolutely should not be the rule for all situations in life. But the ability to discern what situations warrant letting go are a sign of good discretion and wisdom.
One alternative: As @RoboKaren noted in a comment to OP, it is unclear that "One remedy would be he takes me on as a PhD student, or provides funding so another professor can supervise me" actually represents a remedy. For what? Financial compensation? If this incident occurred years ago, I would consider this, as economists might call it, "sunk cost." If the expense was not recouped in time, or arrangements made for future reimbursement, for all intents and purposes it is water under the bridge. I highly recommend to let the financial aspect go, especially since the amount is probably not nearly enough to justify all the problems such accusations could cause for you while you are trying to remain on good terms with the department's faculty, who hold the keys to your degree.
On the other hand, if the remedy is meant for your ego rather than wallet, then it seems counter-intuitive that much good would come from trying to renew a relationship characterized by financial dependence on someone who has already let you down once before. It is like stepping on a rake, then years later trying to step on the same rake on the off chance it would somehow make the old bruise hurt less. History tends to repeat itself, and you just might end up with another bruise. Why take a chance when you don't have to? I would suggest the exact opposite, i.e. to put a good amount of distance between you and this professors, so as to minimize the chances of making the same mistake (of relying on them and being burned) twice. Good luck!