Add ConditionMessage class to help build condition messages in a
uniform format and update existing conditions to use it.

Fixes gh-6756