Sauron obteve a maioria de suas informações de Gollum, como é dito em A Caçada ao Anel em Contos Inacabados:
Now Sauron had never paid heed to the "Halflings," even if he had heard of them, and he did not yet know where their land lay. From Gollum, even under pain, he could not get any clear account, both because Gollum indeed had no certain knowledge himself, and because what he knew he falsified ... Thus it was that he dared to pretend that he believed that the land the Halflings was near to the places where he had once dwelt beside the banks of the Gladden.
Quanto a como os Nazgull sabiam procurar por "Bolseiros", o próprio Bilbo disse a Gollum seu nome ( Riddles in the Dark ):
I am Mr. Bilbo Baggins. I have lost the dwarves and I have lost the wizard, and I don't know where I am.
Se Bilbo passou ou não o Anel parece irrelevante; mesmo se ele tivesse (o que ele fez) (e independentemente de quem ele possa ter passado), "Baggins" ainda é obviamente a primeira pessoa a procurar; ele poderia dizer-lhes onde tinha ido de lá. Além disso, o próprio Sauron teria sabido como era difícil passar o Anel de qualquer maneira.
Em relação a um sobrenome diferente, esse realmente foi o ponto do conselho de Gandalf para Frodo em Sombra do Passado :
...you will have to go, and leave the name of Baggins behind you. That name will not be safe to have, outside the Shire or in the Wild. I will give you a travelling name now. When you go, go as Mr. Underhill.
Então, todas as evidências são de que a única coisa que Sauron e os Nazgull sabiam era que o Anel tinha sido tomado por um Halfling chamado Bilbo Baggins . A Caçada ao Anel deixa claro que eles nem sabiam onde estava o Condado (posteriormente fica claro que nem eles sabem o nome dele), e delineia sua busca nos Vales do Anduin e ao longo do Gladden, até que eles sejam finalmente enviados para Saruman (nesta fase, Sauron tinha ouvido falar da profecia em Gondor - " Busque pela espada que foi quebrada ... "):
From these things he concluded indeed that neither Saruman nor any other of the Wise had possession yet of the Ring, but that Saruman at least knew where it might be hidden.
Depois disso, os Nazgull encontram Wormtongue, que é quem finalmente diz a eles onde está o Condado (e seu nome):
Spare me! I speak as swiftly as I may. West through the Gap of Rohan yonder, and then north and a little west, until the next great river bars the way; the Greyflood it is called. Thence from the crossing at Tharbad the old road will lead you to the borders. 'The Shire,' they call it.
Mas mesmo neste estágio não há razão para pensar que eles tenham outro nome que não seja "Baggins", como indica seu questionamento de Farmer Maggot:
"I come from yonder," he said, slow and stiff-like, pointing back west, over my fields, if you please. "Have you seen Baggins?"