Son sólo conjeturas y me limito a repetir lo que han comentado Baloran y Abârmil, es decir, que es posible que el uso del Anillo dejara una especie de marca en Gollum que le impulsara a acudir al origen el "Mal" y que ese mismo "Mal" le reconociera. No obstante, no creo que Sauron supiera de la existencia de Gollum antes de que éste llamara a su puerta, por decirlo de alguna manera: tal vez lo hallaron merodeando, lo cogieron prisionero y le sacaron lo que sabía, simplemente por el hecho de pasar por ahí. La otra posibilidad es que Sauron recoociera ya inicialmente a Gollum como un Portador del Anillo cuando entró en su "área de influencia" y que fuera requerido a su presencia. Véte tú a saber. De todas maneras dudo que conociera el uso del Anillo por parte de Gollum en las Montañas Nubladas o sus fechorías en el Bosque Negro antes de marchar a Mordor.

Hay un fragmento en LCDA, I, 2 que aunque algo ambiguo, aclara algo al respecto:
[quote]»Gollum no me dijo en qué había estado ocupado. No hacía más que llorar, llamándonos crueles, entre gorgoritos; y cuando lo presionábamos gemía y temblaba, restregándose las largas manos y lamiéndose los dedos, como si le dolieran o como si recordase alguna vieja tortura. Pero temo que no hay ninguna duda: Gollum había ido arrastrándose paso a paso, milla a milla, lentamente y al fin había llegado a la Tierra de Mordor.


Hubo un pesado silencio en el cuarto. Frodo alcanzaba a oír los latidos de su propio corazón. Hasta parecía que fuera todo estaba en silencio. Los tijeretazos de la podadora de Sam habían callado.

-Sí, a Mordor -repitió Gandalf-. ¡Ay! Mordor atrae a todos los seres perversos y el Poder Oscuro pone toda su voluntad en reunirlos allí. El Anillo del enemigo dejaría también su marca, preparando a Gollum para cualquier requerimiento. Todo el mundo hablaba de la nueva Sombra en el Sur y de cómo odiaba al Oeste. Allí estaban sus nuevos amigos, que lo ayudarían a vengarse.

» ¡Tonto infeliz! En aquella tierra aprendería mucho, demasiado para sentirse cómodo. Tarde o temprano, cuando estuviera atisbando y acechando en las fronteras, lo apresarían para interrogarlo. Creo que así fue. Cuando lo descubrieron, hacía tiempo que había estado allí y se preparaba para regresar en alguna misión malévola. Pero eso no nos interesa ahora; el daño principal ya estaba hecho.[/quote]

Saludos desde Tejonera.