775...? The temp limits vary by a few degrees depending on specific model.
Here's a good specification summary with max temps:
http://users.erols.com/chare/elec.htm
Search for "P4-xxx" where xxx is 571, 670, etc.
I'd want to know working temps. Fire up the
http://folding.stanford.edu/download.html client for a couple minutes.
You mentioned there wasn't anything under the HSF. There should have been a small square pad of conductive material. It's protected until you remove the heatsink from the packaging. If you don't have either a pad or grease, or if something got stuck to the pad, then that would cause high temps.