After weeks of struggling with "Contact customer support" and momentarily giving up, it finally worked. I screwed up iMessage when I first fiddled with Hackintosh and my account was probably flagged. So I followed this guide 100% and did all the steps correctly from the iDiot's guide but still same result with the 12 character code/contact customer support.
I made a new iCloud account on my iPhone, but I was also presented with Contact customer support with the 12-char code one second after logging in (I was automatically logged out). I made sure there was no trace of my old log in attempt and even clean installed each time as a precaution/used a different wifi network and generated new smUUID/SN/ROM/MLB info from the guide. I contacted customer support and they refused to help me without serial number after 3 different reps on different days (I called from different phones as a precaution), saying that the code I gave them didn't give any results and they can't do anything without serial number.
I have a legit Macbook Air, and I could not log into iMessage on it with my newly created apple id (12 digit code on the MBA) so I think the accounts created associated with my iPhone were flagged when it came to iMessage. I could use iCloud on all accounts with no problems.
On a whim, I followed the guide one more time (no different than the other times I did it) on my hackintosh but used an apple ID I created maybe 8 years ago that I used only for an iPad and it worked very easily.
So I think that all iCloud accounts that were created from my iPhone were blacklisted because I screwed up the first time. I hit my maximum iCloud account limit that was created from my iPhone (I actually only made 2, but it says 3 is the maximum online), so maybe there's an algorithm that detects suspicious activity and blocks on a higher level (device level).
I could maybe test this theory by creating a new Apple ID/iCloud account on a different iDevice and see if it works, but not going to risk a working iMessage right now.