If you're nodding your head right now, you'll be happy to know we all can cut back on the pain killers. For the first time in a while, I actually received a helpful message from Apple's email support that said something more than "try rebooting." Turns out that, unfortunately, if you enable Mail's random signature feature on one Mac, Mail can't be running on other registered Macs for the first sync after this new feature. I replied to the support rep's email to find out what is up with such an odd quirk, but I didn't receive a very useful answer.
Nevertheless, after getting back to square one by resetting my signature data on both Macs, I can verify that this fix works. Hopefully, this issue is on the list of updates coming in 10.4.4.