Have you tried soaking the hat and sticking in the freezer to prepare it for a run? Works better with a more absorbant traditional baseball cap than a fancy, quick evap tech runner cap. It doesn't provide long-term relief but I certainly delays the feeling of being way too f'ing hot.
I've done that in the past. It might be worth another try.
I have a homemade cooling vest that I have experimented with. You can wear it before a run and it seems to delay overheating a bit. It is also nice to put on after a run in the heat.