Renewal link mangled by webmail client with ISP
Here is an answer that explains the prefix  https://webmail.west.cox.net/do/mail/message/ that was added to the front of our primary domain. Looking at the CiviMail source for this message (and a number of other similar messages, propagated by copy/paste) the mail source did not specifically set the protocol prefix to "https://". Instead, the source had the default "other". Evidently, most of the ISPs we tested tack just http:// on the front and since we redirect that to https://, everything works. However, the ISP cox.net adds a bit more when the link isn't fully specified. We can't really blame them and there may be different prefixes added by other ISPs. LESSON LEARNED: make sure you add https or http protocol when inserting the contact checksum link (hopefully noone is non-SSL, so it really should be https ;))