After Clu's coup d'état did programs know that Flynn didn't exit the Grid? Clu knew, because he was looking for Flynn and eventually used tactics to try and draw him out. But did the population at large know that Flynn was lost somewhere in the Grid?
The grid's population thought that Flynn was either dead or that he had abandoned them to flee the grid.
Remember that Flynn hid himself, and he did it very well for a very long time. In the programs' view, he became some kind of mystical god that everybody had heard about but nobody had actually seen since he vanished. Castor also mentions that the faith in the user was going downhill since Flynn's disappearance. It becomes, as some would say, a sad devotion to an ancient religion.
I believed in users once before.
Also, just before the light-cycle battle, Jarvis goes into a speech where he mentions that the presence of a users was barely a rumor :
Oh what a location we have here before us.
Because, your rumors are true.
We do indeed have in our midst, a user.