They literally tried everything to solve this issue. In the end they said me to send a text message to a number 48369 with a text HELP. A message was not delivered. According to them it means problem is on my provider. I contacted my provider then. This number is not supported outside US and Canada, so obviously it could not be delivered.
They think it is a problem with an international text message to activate iMessage. Trust me, it is not. I sent dozens of them since last week. Everything worked fine until 16.5.1 update. After that - it is not.
Seems like many people have this same issue.
What is more - activation message had never been charged before. I am on supported carrier by Apple. Now - it is charged.
Hope they will update iOS soon. I found that 16.5.1 was released to fix a critical iMessage security issue. Obviously something went wrong, cause now it does not work. E-mail ID works fine. Phone number ID nah.