Sorry about not keeping this thread updated. I've been continuing this research in the background, and was offered what I personally think is most likely to be actual derivation of the name:

The accepted etymology for Maeshowe is ON mest(r) haug(r) ' biggest mound'
(mest-r being superlative of mikil-l, with comparative meiri). This certainly makes good sense both from a descriptive and linguistic point of view. What I don't know is when the earliest record is of the Maeshowe name.

Any thoughts or comments? This etymology certainly seems to make the most sense to me - it's fully Norse, and is a decent description of the site.