There's nothing like a good Hiding/Perception thread!
Agreed! It's certainly one of the types of thread where I feel I have something to contribute.
That's what the iron golem in the 4e rulebooks looks like. The one in the AD&D MM is a bit more like a statue cast in iron.
The picture in the 5e MM looks like that too, more like a suit of armor than a statue, but not really enough to be mistaken for one. The 5e iron golem also doesn't have any traits related to appearing to be a statue or anything besides what it is. The AD&D iron golem has this note in its description, "It will stand, non-functioning, as a guard until some event takes place, i.e. until a door is opened, a book read, etc.", which seems to open the door for its use as a DM gotcha somewhat more than its description in the 5e MM. The Moldvay Basic monster, Living Statue, also comes to mind in this discussion.
My take on this is that if an invisible gargoyle fails a DEX(Stealth) check then the PCs might notice eg wind blowing through an invisible statute, or water dripping onto it, or whatever narration makes sense in the context.
My understanding of the False Appearance trait that gargoyles and certain other monsters have is that it grants the ability to hide in the open because it takes care of sight-obscuring circumstances for the creature. The result of the gargoyle's DEX (Stealth) check then determines whether it pulls off the ruse or if some twitch or other small movement or noise gives it away as not really a statue. In the case of an invisible gargoyle, False Appearance is redundant because the visual component is taken care of by invisibility, so a failed DEX (Stealth) would simply reveal the presence of a creature just as it would had the gargoyle not been invisible.
(I can't get help from either AD&D - the MM says nothing about gargoyles looking like statues - nor 4e - in 4e a gargoyle's stone form gives it DR and regen, but doesn't affect its ability to Hide or Bluff.)
It seems that in 5e the role of "Living Statue" was grafted onto the gargoyle but not the golem. For a golem that's meant to resemble a statue, I'd add False Appearance to tie that narrative to a mechanic.
Anyway, as you suggested upthread, an invisible statue seems likely to cause some alarm. Personally if a creature has the ability to look like a statue, I think it undermines that stealth capacity by then turning it invisible!
Right, it's mostly redundant! The main advantages in using invisibility, however, are not having any sort of visual presence (which in the case of a blown Stealth check doesn't matter), and not immediately revealing what the creature looks like when its Stealth check is failed.
With respect to the higher DC - it would be easy enough to rule that the golem has Advantage on its attempt to hide, giving it a +5 on a passive check and hence an overall result of 14. But you seem to be contemplating "super-advantage" that (to some extent) goes contrary to bounded accuracy in the strictest sense - are there other context, outside of hiding/perception, where that would make sense?
If calling for a DEX (Stealth) check, I wouldn't use a passive score for the result, but rolling with advantage (or disadvantage) is something I might consider under the right circumstances. Setting a DC for a task not otherwise covered by the rules, however, seems to be one of the primary jobs of the DM in 5e, so my recommendation to set a DC to find the invisible golem by normal means of Perception was directed at those who might feel that the difficulty of doing that was unrelated to the golem's ability to hide, the idea being that the golem isn't making any particular effort to escape notice, but rather shares certain qualities with objects. On the other hand, some of the posters in this thread seem to take issue with there being any possibility of noticing the golem without resort to some extraordinary means, such as use of
true seeing or spreading flour all over the room, so that simply staying alert for hidden foes would result in an auto-failure. This falls within the DM's role of deciding whether a result is certain or requires a roll to determine the outcome.