[Formendacil]

As to what Gandalf was doing in these years, we can say a couple things, though they are rather general indeed...

1. Gandalf never wanders east. In his list of names ("Mithrandir to the Elves, Tharkûn to the Dwarves, etc.), Gandalf says, and I paraphrase, "to the I east I go not." In "The Istari" in Unfinished Tales, Tolkien tries to decide where the name "Incanus" comes from--Gandalf's name in "the South" in that same list. Tolkien gives a possible Haradric derivation, but seems somewhat doubtful that Gandalf ever travelled far enough south to earn an enduring name there, and offers the suggestion that Incanus was his name in Gondor--a name that fell into disuse when he stopped visiting there, after which Mithrandir became current.

(Speculation: Mithrandir, we know, is Gandalf's name among the Elves. Since we know that Gondor in the era of the Stewards did not have contact with Elves on any sort of frequent basis, could it be that they came to use the Elvish name for the wizard as a result of Eärnur's expedition to Eriador, when he joined with Elves from the Grey Havens and Rivendell to destroy the Witch-king. This was the last recorded contact between the South Kingdom and the Elves of Eriador. If Gandalf had been involved in any way, it stands to reason that he would have been known by his name among the Elves (and the Northern Elf-friends): Mithrandir.

This would coincide with Tolkien's speculation on the name Incanus as one that Gandalf had in Gondor early in his time in Middle-earth [say 700-900 years before Eärnur's time] that fell into disuse later.)

2. Gandalf tells Frodo in "The Shadow of the Past"--and, again, I paraphrase--"that about their origins, at least, I know more than Hobbits do." Gandalf says this in the context of telling Frodo that Gollum was basically a Hobbit. The implication is that Gandalf is familiar with the fact that the Hobbits had come west over the Misty Mountains, having lived in Anduin's valley where Gollum seemed to hail from.

Even if Gandalf did not develop his deep love and interest in Hobbits until after they had settled in the Shire, it would not be surprising at all for him to have had at least some contemporary knowledge of them when they lived in Anduin's vale or were found in communities on both sides of the Misty Mountains. After all, we know that the Hobbits started moving west because Greenwood had started turning to Mirkwood--an event contemporary with and seemingly linked to the arrival of the Istari at the Grey Havens. While the wizards may not have found anything to link the growing darkness in Dol Guldur to Sauron at that time, it seems greatly unlikely that they would not have been snooping around that neighbourhood looking, and the proto-Hobbits were definitely in that neighbourhood.