Just to include one last information inside of the @SilverNija - MSFT post. After do something like this:

 var customCat = "Custom Category";
 if (mailItem.Categories == null) // no current categories assigned
   mailItem.Categories = customCat;
 else if (!mailItem.Categories.Contains(customCat)) // insert as first assigned category
   mailItem.Categories = string.Format("{0}, {1}", customCat, mailItem.Categories);

Don't forget and it is the most important, to update the instance of the mailItem this way:

mailItem.Save();

Because, there is an issue that sometimes a bunch of mail items are not updating when they are inside of a loop, so it worked for me to solve this problem.