When I got married to my now Ex a few years back, we had checks in just about every configuration you can think of. We did already have a joint checking account though, so I'm sure that helped. I wasn't changing my name, and I have a nickname that is not on legal documents/accounts.
We didn't actually have trouble, surprisingly, with ones that said:
Hisfirst and Myfirst Hislast
Hisfirst Hislast and MyNickname (no last name)
Myfirst Mylast and HisFirstMisspelled
Hisfirst Hislast and NameThatStartsWithTheSameLetterAsMyFirst MyLast
Now, I don't know if that was because we had a joint checking, or because we came in with what was quite obviously a stack of wedding checks, or because the teller made a judgment call, or all three.
But since others may not have such a forgiving teller, I would:
1) Never use titles. They muck up the check for no reason.
2) Use both names and an "OR" so that either may cash it
3) Use pre-marriage names, even if you know she's changing hers.
Not only is name change not often instantaneous when you *are* changing it legally, but there are many women who change it socially and not legally. Even if every indication is that she's changing her name (being announced at the wedding as Mr & Mrs Hislast, etc), that still only tells you she's changing it *socially*. You don't actually know a thing about her legal name status unless she tells you outright. Addressing Christmas cards and checks are completely different exercises.