Think that this 'moon stain' was a result of the belching smoke from that mysterious Shire locomotive driven by the talking fox...
Guess that it's just a literary device (if I'm using that right).
You look at the moon and see 'stains,' as, looking down at your shirt after a sumptuous dwarven meal, the food and beverage that wasn't caught in your beard now decorates your shirt. Stains don't appear when something is new, like when you took your shirt out of the drawer and put it on that morning, hence the moon must be old as it looks more like your post-meal shirt. If your shirt could have once been clean (even if you never remember it being otherwise
), then so could the moon. Just another way of indicating time's passage; time's arrow where we go from pristine clean to cluttery dirt. Entropy.
Whatever; what did cause those stains in Tolkien's cosmology? Asteroids? Melkor? Or does Tilion need a bib?