Working through the issue right now as a matter of fact
. Although I have a "hot" FE versus your 351. I have swapped out the radiator and fan for the larger core and higher CFM as part 1. That got me down from the 100-110C range to 90-95C...which is ok.
Part 2 entails replacing my 180F tstat with a 160F tstat as well as replacing the fan switch with a lower set point (77-82 deg C) so we catch the heat rise sooner. I would try my "part 2" first. .. Changing out the tstat should do the trick.
The engine heat soak was also causing vapor locking and hard starting.