Yes, but keep in mind that they both pretended to be half-Genies (which Holly actually used to be when she was alive), not full Genies. In HGH the mayor talks about how there are ¨many Half-Genies protecting towns these days¨ or something among these lines.
It was said that they were the protectors of the labyrinths but were imprisoned by the bosses.
Yeah I have to admit that it was pretty ignorant of me to write that. In the game's good ending the messenger clearly stated that the Genies are supposed to stay in the Realm to protect the physical world. It was never said that they can't travel to the physical world if there's a good reason to do so, like informing Shantae. But it makes me wonder if the Genies have some kind of ruler, some kind of Genie counterpart to the Sequin Land Sultana, who tells them when they are allowed to visit Sequin Land.
In the manual for the first game it's written that ¨he made many tremendous discoveries, including Shantae¨ so yeah.
Talking about the Shantae manual, there's something quite interesting in there regarding flying carpets: there's a drawing (most likely by Matt Bozon) of Shantae lying on a flying carpet in the background of the Contents page. This means that the flying carpet concept for the series was alive a full 14 years before we finally saw them in-game.