Bandits won't move once spawned, but creatures will. If your perception is down low, and your ship sensors are low, it's very likely you're just missing where the creatures are. That's happened to me several times, where I just kept flying around on the new square finding nothing, only to find the one pack of Kaadu off in a corner somewhere. On the slabs I've used scouts on, I've never had a no-spawn unless there was already a PC on the terrain.
Drop some scouts, perhaps, with Sensor Packs and see if it really is your perception.
I don't think that the Spawnchance has anything to do with PC perception itself. They spawn whether or not you can see them immediately.