Well I replaced the aux fuse and warmed the car up. The aux fans are acting differently now. With the ac on, both aux fans come on low speed with only a little rise above normal operating temp. I took it out on the highway and ran it a little. Brought it back home and watched it at idle some more. It's about 80F outside and now the needle on the temp gauge is not moving much above the 85C mark. Before, even after I replaced the radiator, coolant, and thermostat, the temp was going above the unmarked white line between 85 and 120 before the aux fans kicked in. Now, even after idling a while, the temp is staying pretty constant, with the aux fans cycling on and off early.
I guess the aux fuse really was intermittent -- to the point that the fans weren't able to kick on early in the temp rise. Anyway, I think it's now fixed. I hope this someone with similar problems.