I've been troubleshooting this exact problem the last four hours without any luck. I have run through this guide several times and the only step I've skipped is the "
checkcoverage.apple.com" section where I'm supposed to see the "
We're sorry, but this serial number is not valid. Please check your information and try again" prior to continuing. The reason I skipped this step is because the website seems to be down, all I see is "we'll be back soon" every time I load the page from any device. I assumed if I skipped this step, I would be unlucky only one or two times before getting a good match with the serial/uuid. However, that's not the case. It's been a good 7 or 8 combinations and I'm still having the same issue as you mentioned, where I see the recipient in red and I get the "_____ is not registered with iMessage".
One thing I noticed is that when I run iMessageDebug and save the .txt, the UUID inside that file isn't and hasn't been identical to the uuid that's saved in my config.plist. However, everything remains identical when I run iMessageDebug after a restart and compare it to the saved .txt.
Am I extremely unlucky here and have not found a successful serial/uuid combination in the 7 or 8 tries or do we think it may be something else? Also, is "checkcoverage.apple.com" reading "We'll be back soon" message to anyone else or is that just me? Could this verification be what's preventing me from successfully getting iMessage to work? I have gotten iMessage to work (with this guide) on my last install over the weekend, but since I'm running a new SSD, I have to get everything working again. If anyone has an input, I'd really appreciate it.