I looked up "maes" in the Index of Celtic and Other Elements in W.J.Watson's 'The History of the Celtic Place-names of Scotland' (by A.G.James and S.Taylor incorporating the work of A.Watson and the late E.J.Basden) and it said:
Maes (Br, Corn, W), mages- (eCelt), mes (Corn), meaz (Bret), mutated faes, Angl moss- field, plain
How is listed as meaning "low hill". So, from those definitions, Maes Howe would simply mean "Plain with a low hill" - which does describe the setting pretty well.
Mess is referenced to Mae, Mass has no entry and May is listed as an anglicized version of the Irish meidhe - meaning neck, stump or trunk.