Check the fan speeds and be sure that there isn't any "silent fan" profile somewhere. If the fans are spinning at 100% with that temps you will definitely need a new cooler but in this case I guess you had terrible luck with the silicon lottery or maybe the thermal paste between the die and the IHS is not enough (factory issue). Also if the airflow in the box is terribly wrong this can happen but it is very unusual, just a single fan in the back taking the air out should be enough.
You will probably be able to ask for warranty to Intel (I think they give 4 years for any processor in the entire world) pleading for very high temperatures.