We all need to keep in mind that the vast majority of divers are infrequent, recreational divers. Unfortunately most of these individuals (of which I could be classified at times) do not take the time to so much as think about diving or re-certification. The fact is, people go on a trip, get certified, dive a few times and stop. A year or two later, and sometimes many years later, they go diving again. As a result many people would be up for re-certification just about every time they dive, which isn't going to keep people diving.
As I see it, the most feasible solution is instructors who help their students understand the dangers of the sport, and the steps necessary to be safe. A well trained, or at least well informed diver should know that a long lapse in diving necessitates a refresher or at least diving with an instructor/ dm. Boats and resorts can also help in the process without forcing people who want to do a casual dive to produce documentation that they may not care to have (logbooks are after all optional last I checked). I've been on boats where anyone without recent dive experience was more or less forced to do an intro dive until they passed a visual inspection.
Lastly we, as informed divers can have an impact. Rather than just talking to our own buddies or taking a "it's not my business stance", when you're out on a boat or talking to another diver and they mention their experience, or lack thereof, remind them about the importance of refreshers. We've all been around someone who hasn't dove in years but can't wait to jump back in, and even if we can't stop that individual, we can take a few moments to remind them of the basics. After all, I'd hate to see the guy next to me get airlifted out because he had forgotten that you're suppose to exhale on assent.