I've recently discovered that Chapter 12 of Deathly Hallows tells us that Grimmauld Place has been hidden to muggle eyes for a long time:
The Muggles who lived in Grimmauld Place had long since accepted the amusing mistake in the numbering that had caused number eleven to sit beside number thirteen.
This suggests that the building has been hidden for longer than The Order has used it for. This means that it must have been hidden prior to Dumbledore's Fidelius Charm on it.
However, chapters 3 and 4 of Order of the Phoenix seem to very strongly imply that the house became visible to Harry only when he had learned the secret that was the target of the Fidelius Charm:
Harry looked down at the piece of paper. The narrow handwriting was vaguely familiar. It said:
The headquarters of the Order of the Phoenix may be found at number twelve, Grimmauld Place, London.
[...] Harry looked around at the houses again. They were standing outside number eleven; he looked to the left and saw number ten; to the right, however, was number thirteen.
"But where’s — ?"
"Think about what you’ve just memorized," said Lupin quietly.
Harry thought, and no sooner had he reached the part about number twelve, Grimmauld Place, than a battered door emerged out of nowhere between numbers eleven and thirteen
So what is actually responsible for hiding the house? Deathly Hallows seems to say that it can't be Fidelius, but Order of the Phoenix strongly implies that it must be.
The natural guess is that there are two layers of protection - whatever existed previously and then the Fidelius Charm - but, if that is the case, then why does Harry knowing the secret - something that doesn't actually mention the existence of the house - defeat all of these protections? Are we to believe that the only other relevant protections on the house are strictly anti-muggle? If so, then how can we explain The Order being concerned about Bellatrix being able to find the house in Half-Blood Prince, where the Fidelius Charm (which, by assumption, is the only relevant charm protecting the house) should have protected it fully?