All good advice. I’d add that becoming good at “selling” your work is key. To me the best way to gain approval is to gain your clients’ respect and trust (using many of the the things you list here) and then “sell” them your design decisions. I use the word sell pretty lightly. What I do is explain and strongly defend my decisions when I’m presenting my work, kind of like establishing a legal defense. Be sure and take the time to explain and educate why decisions were made, etc. If you’ve done the things you mention above this is usually fairly straightforward.

The advice about having written explanation is also great – I don’t know how many times I’ve had something approved only to find out that it needed to be presented again to someone else without me there to control the feedback.

Another tip: tell your clients that they’re going to approve the design. Don’t ask them. Again, if you’ve done a job you’re willing to stand behind, and you’ve built that trust and respect, this almost always results in very quick approval. :)