Have the guy lurking do a stealth check?
How often should the characters do a perception check? Once every minute, once every 10 meters? Did they even state that they were trying to perceive anything? Do you only have them do a check when there is something worth noticing? Doesn't that give away that there is something they should be noticing? Do you check each and every person they see on the street to perceive if there is something odd?
Did all the PC's indicate what direction they were looking?
If the characters even see the guy, do they think anything is out of the ordinary?
Seriously now, check out the following threads
http://www.mongoosepublishing.com/phpBB2/viewtopic.php?t=40325&highlight=perception+recon
http://www.mongoosepublishing.com/phpBB2/viewtopic.php?t=37139&highlight=perception+recon
The key, IMO, is if it's part of a plot, it shouldn't be left up to skills and die rolls. That said, IMO, certain things should be left to the characters abilities to notice something, and not the players.
hmmm, I'm not making any sense. Nothing new there.