I don't really practice full time SEO. But the sites we build here are very SEO friendly (when they need to be). After that, I try to explain the core basics to clients. Many of them get it, some it takes longer, but most eventually get it.
There are some that just do not get it. They just will never understand.
What do you do when your clients just don't get it?