As I mentioned previously, the Microsoft Tag HCCB format - which is CMYK by default - has been tested in various monochrome formats. Since then, however, I read about the 'palette symbols' - the final four triangles which are the same in every Tag and therefore enable the decoder to handle many color reproductions (once it figures out the bounds and orientation of the tag).
To test out the palette's influence on the decoder, the tag shown to the left has been recolored and then "read" with the Tag Reader application for iPhone.
Each of these versions: Red, White & Blue; Purple, Yellow & White; Blue, Lime & White was decoded successfully. Admittedly the conditions were 'perfect' (represented on screen, photo taken square-on and filling the viewfinder, etc) but it does suggest the format is less sensitive to specific colors than it seems.
I'm sure Microsoft put a lot of thought into standardizing on CMYK though - probably not a great idea to put one of these 'custom color' tags into the wild...
[EDIT] Interestingly, there is some sort of error correction or extraneous symbols in the current implementation too - a couple of my Tags (including the one shown above) work with the bottom row 'blacked out' (but not the 'palette' symbols) like this: