Orkney Railways

[Struner]

[...]
I went on holiday to Malta a couple of years ago, and didn't know whether to say "in Malta" or "on Malta".
[...]

I suppose is was both? You were in the country called Malta & on the island called Malta? Or did you stay on one of the other islands?
The name Orkney is a plural itself, from Norse Orkneyjar - supposed to mean Seal islands. So Orkneys is a plural of a plural (a plural squared ).
You would simply say on the Mainland - always with the definite article. & from a distance, on the mainland of Orkney or on the Orkney mainland.
The other mainland is mainland Scotland - or simply the South.
As for Gairsay, it's worked as single farm. I would think within Orkney they would say "I belong to Gairsay", but elsewhere "I'm from Orkney".
& there is Marjolein from Shetland (wait for the bonus):

 

[RLBH]

You can circumvent the latter issue by arguing that any map of Scotland that doesn't show Rockall is merely an excerpt anyway, so you can stick Shetland wherever you like (within the limits of cartographic good taste).

Not any more, at least not on government work - it is the policy of the Scottish Government that Shetland may not be put in a box wherever it suits the mapmaker, but must be in its' correct geographic position!