Why did he need to wait in Albania?
True, Auror's were searching for him, but he could hide himself in animals, could he not? If I were him, I'd hide myself in, say, birds, and fly right to Lucius Malfoy's house.
Aaah... pain beyond pain, my friends; nothing could have prepared me for it. I was ripped from my body, I was less than spirit; less than the meanest ghost... but still, I was alive.
-Harry Potter and the Goblet of Fire, chapter 33
He was very weak; it would take effort to find a Death Eater who was still loyal and not in Azkaban.
I sometimes inhabited animals - snakes, of course, being my preference - but I was little better off inside them than as pure spirits, for their bodies were ill adapted to perform magic... and my possession of them shortened their lives; none of them lasted long.
So would you want to risk having your host die over the ocean where it would be almost impossible for someone to find you?
...and I had given up hope, now, that any of my Death Eaters cared what had become of me...
So there were several reasons why he didn't go looking for them.
There's also no reason to assume he could talk while possessing an animal. And even if he could, would you believe if a little bird flew up to you and claimed to be the Dark Lord? :P