I have a brand new system with a Pentium g3258 processor, and a Corsair H100i cooling it. Despite it being a low TPD chip and a rather overkill cooler, the processor runs very hot, specifically on the stress test and worse on the bench-marking test. (both in the intel comand software) I planed to overclock this chip, but if it is already this hot i'm not sure it's a good idea.
My hope is that it is poorly applied thermal paste or something similar to this. I haven't had a chance to check this, but i will update when i have time.
Like you said, it is most likely poorly applied thermal paste.
Nonetheless here are some other issues there could be:
1. The water cooler doesn't have enough water in it.
2. It might be overclocked without you knowing it. (system glitch; use CPU-Z to see whether that is happening or not)