[The Might]

Ok, now firstly to Malbeth.

I personally doubt it was Gandalf, we would have probably known that or Tolkien would have hinted towards it with some other acts of magic by Malbeth.

What he is most surely in my opinion is of Numenorean descent, simply by looking at his age.

He made the first prophecy in 1864 (according to HoME the birth year of Arvedui) and the second during Arvedui's reign, meaning after 1964. That is a hundred years span, surely showing that Malbeth had Numenorean blood.
But don't try and use his age as an argument for him being Gandalf, it was actually a normal thing, since for example Araphant, Arvedui's father lived 175 years, so it's ok for Malbeth to have made the prophecies 100 years or more apart.


Ok, now with that finished, let's take a closer look at Gandalf and what he did all that time.

There is, as far as I am aware of, one single more clear hint as to what Gandalf did all that time between discovering the shadow over Mirkwood around 1100 and 2060 when the Wise realised it might be Sauron over there in Dol Guldur.
But, it only remains a hint and nothing clear is stated:

If we assume that he first visited Gondor, sufficiently often and for long enough to acquire a name or names there – say in the reign of Atanatar Alcarin, about 1800 years before the War of the Ring – it would be possible to take Incánus as a Quenya name devised for him which later become obsolete, and was remembered only by the learned.

It's only something assumed and although it makes sense, it cannot be proven to be true, that is certain.

We must simply believe what is said, that

though he loved the Elves, he walked among them unseen, or in form as one of them, and they did not know whence came the fair visions or the promptings of wisdom that he put into their hearts.

Concerning the area he walked it, two quotes are of interest:

"The North" thus includes all this great area: roughly West to East from the Gulf of Lune to Núrnen, and North and South from Carn Dûm to the southern bounds of ancient Gondor between it and Near Harad. Beyond Núrnen Gandalf had never gone.

But his main province was "The North", and within it above all the North-west, Lindon, Eriador, and the Vales of Anduin.

As to what he exactly did, well:

He may have attempted to gain the Haradrim on his side, with little success though as it seems, maybe a mission similar to that of the Blue Wizards in the far east.

But the southern regions in touch with Gondor (and called by men of Gondor simply Harad "South", Near or Far) were probably both more convertible to the "Resistance," and also places where Sauron was most busy in the Third Age, since it was a source to him of man-power most readily used against Gondor. Into these regions Gandalf may well have journeyed in the earlier days of his labours.

Anyway he does not seem to have lingered there long, perhaps because he was received poorly and people did not trust him over Sauron.

At any rate it seems unlikely that he ever journeyed or stayed long enough in the Harad (or Far Harad!) to have there acquired a special name in any of the alien languages of those little known regions.

He appears to have neglected Gondor, though as seen above he did probably visit it or at least pass through it at times:

Gondor attracted his attention less, for the same reason that made it more interesting to Saruman: it was a centre of knowledge and power. Its rulers by ancestry and all their traditions were irrevocably opposed to Sauron, certainly politically: their realm arose as a threat to him, and continued to exist only in so far and so long as his threat to them could be resisted by armed force. Gandalf could do little to guide their proud rulers or to instruct them, and it was only in the decay of their power, when they were ennobled by courage and steadfastness in what seemed a losing cause, that he began to be deeply concerned with them.

So, all in all, I'd say he just wondered around, mostly in the west and the north-west amongst Elve, Men and Hobbits, all hostile to Sauron's darkness and tried to help and counsel them as he could, whilst he was gathering information about the shadow in the east. It appears clear that he was not expecting Sauron, this idea was first mentioned in 2060, but he may have built up a case to convince the Wise of the importance of an attack.

Lastly, I support the idea that Gandalf as a life-long traveller gave some tips to Aragorn before he set of on his own adventures in the wild of Middle-earth and perhaps also gave him the idea of using a false identity to hide his heritage. However, both this and any suspicion about some encounter with the Witch-king are plausible, but cannot be proven true with quotes from the texts.

That is all!