Well, you could have units move around in a rectangle, like so
You could also get a little bit more crazy, going beyond just a rectangle and adding sudden turns and such to your circle of creep patrol.
If you wanted to make it very difficult, you could have the units switch the direction of their circle of patrol every now and then.
That's also a good idea, but it's still not exactly what I mean. I'll try an illustration along with some captions:
|---------------------------------------------------|
| X~~~~A | Y |
| | ~ |
| | ~ |
| |__B_______
| |
|---------------------------------------------------|
The box is the map.
X is a footman and the beginning of footman X's patrol.
Y is a footman and the beginning of footman Y's patrol.
A is the end of footman X's patrol.
B is the end of footman Y's patrol.
~ is a patrol-path.
- is a wall.
| is a wall.
Make X patrol; Y is not on the map. When X gets to point A, remove him. When you remove X, create Y. Make Y patrol to point B. When Y gets to point B, remove him. Create X at point A. Make X patrol to point X. When X gets to point X, remove him. Create Y at point B. Make Y patrol to point Y. When Y gets to point Y, remove him. Create X at point A. Etc.