Hmmmm...
Holy hell, I don't know. With that setup, and 20 bots, it should remain silky smooth all the time. The Halflife engine just isn't that taxing on a xp16 and Ati8500.
Sounds like a really stupid driver problem, or the vsync is (for some reason) pulling you back. It shouldn't; but it's possible.
Besides, at 40fps, it shouldn't be choppy. It doesn't start to get noticably choppy until right at 30fps.