Isn't it possible to find every camera OSD update routine and add a hook to refresh the CHDK OSD as well or something?
Not really. The camera code is (mostly) executed directly from the cameras flash ROM. CHDK hooks a few tasks, by implementing the entire task up to the point we want to override in the CHDK binary (which is loaded in to RAM) We cannot arbitrarily replace all use of a specific function for the whole Canon firmware. We could do that if we actually flashed CHDK into camera ROM, but the risks of bricking cameras would be much much higher. Definitely not worth it for a cosmetic thing like this!
As I said earlier, the amount of flickering varies because the Canon firmware updates more or less frequently in different situations. It's unlikely that anything about CHDK builds actually affect it. There is a define (CAM_DETECT_SCREEN_ERASE) which helps CHDK know when it needs to redraw, but this is currently enabled for all cameras.