As Kendall said, they only spawn when you enter the grid. So if you kill all the creatures/bandits in a terrain square, you'll need to leave and reenter or travel to another terrain square to find more. The best setup is usually to have 2 empty grids that are adjacent to each other and alternate between them.
It's implied in their answers, but for clarity, any PC on the terrain will cause the creatures/bandits to not spawn. I believe it doesn't matter if the PC is active/inactive/arrested, as long as they're on the terrain square (in a Ship or actually ON the terrain) it stops the spawning. I'm not 100 % sure on the inactive PC though.
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.
Each Terrain type has a percentage of you finding a creature on it. It is more likely to find creatures on certain types of terrain. For more information on what creatures can be found on each terrain, look at Creatures
List of Terrains and their percentages:
Black Hole Terrain 0%
Gas Giant 1%
Sun Terrain 0%