Yes, it will work.
Flicker perception is incredibly subjective. Back when we used CRT computer monitors, 60Hz was unusable for me, but I know loads of people who didn't notice a problem. At 85Hz, I could still detect flicker in my peripheral vision if I was close to a large screen. Of course, "large" was 20 inch or so, back in those days.
Personally, I'd agree with 100Hz for PWM. Perhaps higher. Depends on what your eyes, depends on what your micro+code allows... I did a fading light things using a 16F84 many years back, and went for something in the region of 200Hz IIRC. You are right to say there might be non-linearities - I used a lookup table to decide on different values for the PWM code. Our eyes are as non-linear as our ears...
CRT TV sets did not refresh at 25Hz. They were interlaced, so the field scan was 50Hz (or 60Hz in some parts of the world, of course). Flicker in peripheral vision was one of the problems with bigger screens. Though ironically, flicker does help with motion portrayal, which is why some professional LCD screens use tricks such as pulsing backlights or blank frame insertion.