I'm now quite certain it is a carrier issue. Many people here have followed all of the steps to fix imessage without luck.
How many of you having problems, are on a number ported to telecom?
eg, I am on an 021 number, ported to telecom.
Good point, too. I'm on a ported 021 to Telecom as well.