I find it useful to speed up the default Arduino PWM by changing the clock source. There are some useful details at http://www.righto.com/2009/07/secrets-of-arduino-pwm.html . Basically you should be able to drive it up to tens of KHz. I'm not sure how far up it remains linear but works well enough for lighting.

At default clock rates (clock/256) I can definitely see the flicker, especially through the lowest duty cycles.