Spinning the water pump faster?

I assume you already checked that you aren't running lean at idle. That can generate more heat. Also, engines with a wild cam can be very inefficient at low speeds, which could increase heat losses. The stange thing is that you still have the problem with electic fans. That should be the same as driving at ~30 mph. Blocking the air gaps sounds like a good approach.