Change the Message Table so it points to the Category table.
MessageTable
------------
MessageKey
CategoryKey
Message
Add a MessageSubcategory Table for the one or more sub categories a message might have.
MessageSubCategoryTable
-----------------------
MessageKey
SubCategoryKey
You can get any SubCategories with the following psudeo-SQL:
Select Subcategory
From SubCategoryTable, MessageSubCategoryTable
Where CategoryKey = CategoryKey from MessageTable
And SubCategoryKey = SubCategoryKey from MessageSubCategoryTable