Obviously without Killapps patch or Sfall mod, I go extremely fast across the world map and hardly encounter anything. Because, apparently, the speed of a modern computer can cause this unintended side effect.
But with killapps unofficial patch, I find myself in an encounter every 1 or 2 grid squares. This seems like an awful lot compared to Fallout 1. Even without Outdoorsmen as a tag skill, I didn't encounter stuff nearly as often in Fallout 1.
But I wanted to ask, if this was an accurate representation of what Fallout 2 encounter rates are supposed to be like. Or if the modifications made by killapps went too far. Hopefully somebody who played FO2 back in the late 90's with a computer of that era can answer this question.

Your encounter rate depends on your luck score (lower scores mean more encounters, higher scores mean fewer encounters overall but more special good ones), your outdoorsman skill, and your place on the map (some regions of california are more monster-rich than others). I suspect that your encounter rate is also higher when you're moving through unexplored areas, but I haven't tested that out. You also have fewer encounters if you're driving in the Highwayman.
I've played Fallout 2 with and without Killap's patch, and in either case an encounter every couple of squares is pretty extreme. Has this been going on long? Or are you just in a bad spell right now?

Well to provide a clearer picture:
My character's luck is 5 and outdoorsman is 20 (not tagged)
I usually make at least 1 encounter from Arroyo to Klamath
About 1 or 2 encounters come up when heading from Klamath to Den
2 to 4 from The Den to Modoc
1 to 3 from Modoc to Vault City
I also must ask: Does this game do level-scaling for random encounters? Because I noticed that the raider/bandit enemies I ran into during this little test (I'm level 1) didn't come in such deadly numbers, or as well armed, as they usually are. Usually I'm level 3 or 4 when I leave the Den and sometimes I get outnumbered and killed while heading to Vault City, without even a fair chance to run away

The rates you just quoted sound okay to me. I had a character with similar stats and a similar encounter rate... although once again, I think that the "explored" status of a square you're walking through might decrease the encounter rate. If you're tired of fighting, try to get that Highwayman up and running ASAP.
As for level-scaling... I don't think there is any, no. The enemies vary in difficulty depending on where you are on the map. The ones on the route between Arroyo and Klamath are the weakest, poorly armed and poorly armored. The ones in southwestern california (mostly Enclave soldiers and mutants) are much tougher. The NUMBER of enemies you encounter might change with your level, though...

The difficulty of encounters depends almost entirely on the area you're in.
Generally, the further south you go, the harder the encounters, but really I reckon it's based on you visiting the towns in a particular order (based on the order you would find out about each town).
Also, when I played it "back in the day", I used to get an encounter approximately every three or so grid squares, depending on a few factors mentioned above.
There is a way of changing an .ini file to reduce the number of encounters that you get with Killaps patch.

There is some. Raiders in random encouners (at least those in caves) have better equipment when you gain levels. I recommend reading through the encounters section in Per Jorner's walkthrough:
http://fallout.wikia.com/wiki/The_Nearly_Ultimate_Fallout_2_Guide
As for the OP's encounter rates I never, ever had any encounters between Arroyo and Klamath. Once I had one encounter between Klamath and Den. But then again I never start a character with anything less then 8 luck.