Gleb, I noticed that you said "Under User Realm - Authentication Policy - Host Checker I checked Evaluate ALL Policies"
If you want the the custom remediation message (or reason strings) to appear prior to authentication you must also configure the policies to be enforced at the realm level. If you are only evaluating the HC policies you are telling the IVE that you wish to keep a record of which policies were passed / failed so that you can use that info in the post-authentication role mapping.
I generally try to avoid enforcing many HC policies at the realm level becuase they can be difficult to troubleshoot. If you are enforcing several HC policies at the realm level and users are not able to remediate the issue/s themselves, you will have to take additional steps to locate their user session logs on the IVE since they were never given the opportunity to submit their username.
Alternatively, I prefer enforcing the majority of my HC policies at the role level. I'll typically have zero or one HC policys enforced at the realm level along with some other non-HC checks (certificate, source IP, user agent).