Loque kept playing Hide&Seek with me all the years through WotLK, but I finally got him in March this year. My tipp for you:
Search in the early morning if you can, 5am-7am or so. I found my Seimei at 06:05am back in March, but I had checked for him the whole night before. And also, if you have an Alt who can travel Northrend, I suggest you to go hunting for other "normal" rares there while yourn hunter is parked in Sholazar. When I camped for Seimei I regularly switched to my Pally and flew over Northrend, searching for other rares in hope to get Loque to spawn - 7 rares later (yeah, 7 other rares that night, nice income of gold and so

) Aotona spawned. At that time i was so frustrated because this bird was never a pet I wanted (didn't liked it in all ways

). But I also did not wanted to kill it, so I tamed Hibiki just to follow my plan on making Loque spawn by eliminating other rares. (And guess what? Yeah, Aotona was named Hibiki, I only name pets which I've clicked with...some strange things happen, by accident I've come to like this birdy.) After this short incident I logged back on my Pally, hunting other rares. Checked via /who every few minutes if someone is in Sholazar, just in case...oh noes! 85er Warlock! D: Quickly logged back on my hunter, 15 minutes after taming Aotona and there he was: Loque'nahak walking peacefully through the apes at the east spawnpoint.
Long story short: Killing other rares with an Alt while hunter is parked in Sholazar helped me to get Loque, maybe it can help you, too? Or let a friend go searching and killing other rares in Northrend while you circle Sholazar.
As to Gondria, I couldn't say much. Only to search early in the morning, too. I found her with my Thara back in WotLK by chance in the morning, Neirana got her one hour after Loque because I flew with my Pally over Zul'Drak and saw the ghostly kitty. XD Maybe just fly over Zul'Drak without expecting her...who knews if it helps?
