**Grimmauld, 12 was used for ages by Black family as a residence**.

The charm hiding the house from Muggles was not Fidelius, but some other (unspecified) Muggle repelling charm commonly used by Wizarding folk to hide their dwellings.

Although it is not explicitly explained in the books, the current Magical law (The Secrecy Act) required any Magical family to use all necessary precautions to prevent Muggles from seeing them doing magic. The best way to do it in a big city would be to make the house totally inaccessible to Muggles. Same way as *The Ministry of Magic*, *Hogwarts*, *Gringotts* and other major Magical buildings in London. As it is explained with Hogwarts, the charms (unspecified) make the place invisible and *unplottable*, i.e. it is magically hidden from any maps or navigation equipment muggles use.

So, Muggles do not see the house at all, they see houses 11 and 13 adjacent to each other, with no gap. 

A similar enchantment is described in Deathly Secrets, where Muggles see some war memorial instead of a monument to James and Lily Potter.

After the house became The Order HQ, however, Fidelius Charm made the house invisible to Wizards/Witches as well, unless they were given access by the Secret Keeper.

The Order's concern about Bellatrix was due to the fact that she might challenge Sirius's (and later, Harry's) inheritance of the house, and enter it as a rightful owner. There is some hole in this protection scheme connected with wizarding inheritance laws conflicting with magical loyalty, and it is due to the fact that the house had many layers of enchantments placed upon by generations of Blacks, and has its own sense of loyalty. You may compare it to Kreacher, who is extremely loyal to the family, but has to obey Harry as his rightful master.

Harry fits all the requirements to gain access to the house. In the events of Order of the Phoenix, he is recognized by the Fidelius Charm, and other protection recognizes him as a guest of the house owner - Sirius Black, who is a rightful heir to the House Of Black. Later, with Sirius's demise, the ownership transfers to Harry by Sirius's will. So again, he fits all the requirements as the rightful owner and the Order member.