[Mithadan]

My comment was pure speculation in the nature of connect the dots.

Gollum was drawn to Mordor. "And sooner or later as he lurked and pried on the borders he would be caught and taken - for examination... When he was found he had already been there long, and was on his way back. On some errand of mischief." The implication appears to be that he was released, but this is not expressly stated. All we know is that while he was at or in Mordor, he met Shelob.

"Already, years before, Gollum had beheld her, Sméagol who pried into all dark holes, and in past days he had bowed and worshipped her..." Gollum was in Mordor years before only when he was caught and brought to Sauron. So he encountered Shelob either on his way in or on his way out.

"And as for Sauron; he knew where she lurked... And sometimes as a man may cast a dainty to his cat (his cat he calls her, but she owns him not) Sauron would send her prisoners that he had no better uses for..." So Sauron was known to do this and might have done so with Gollum.

By the way, does anyone know why Tolkien seems to have disliked cats? Consider the early tale of Tevildo, lord of cats, who later became Sauron.