In your case, while the massive factor of safety in wattage may not be decreasing your odds of failure by any measurable amount, you're getting reputable brand name PSUs and that's good. Even better that you're getting them for a good price. Do keep in mind that capacitor ageing is real, and like all things, the older it gets, the more likely it is to fail. I wouldn't have a problem buying those PSUs for that price if they're <5 years old, but if they're much older than that just get a new one for $25
Heat output of a PSU is a product of the inherent inefficiencies in electronics. If you have an 80% efficient PSU and your system wants 100W, then the PSU is producing 25W of "waste" energy/heat. Assuming both a 250W and a 1000W PSU are 80% efficient at this load, they'd both generate the same amount of waste heat.
All PSU's follow a roughly equivalent Efficiency Curve
whereas they're generally most efficient at 50% of their rated peak output. Higher quality PSUs will tend to have a flatter curve (smaller difference in efficiency over the output rang) whereas low quality PSUs' efficiency can drop off quite dramatically above/below the 50% range. The 80 Plus Certification standards have done a lot to improve both overall efficiency, as well as made PSUs' efficiency curves more consistent.
As a rule of thumb, you'll want to determine the wattage of a system running at typical load (gaming is a good test) and buy a PSU whose wattage is about double that figure. As you said correctly, having more watts than you need is beneficial because it stresses the components to a lesser % of their capability which should
allow a PSU to last longer. However, keep in mind that if you're following the typical guidelines, your PSU should already have a (roughly) 2x factor of safety already and there's definitely diminishing returns in play. Buying higher wattage PSUs is not a good substitute for buying higher quality PSUs.While a 750W PSU can power a system that only draws 100W under load, it is doing so at 14% of its rated capacity....and that's the most the system is going to draw. You're operating at the absolute worst point in the PSUs efficiency curve (in today's 80 Plus Bronze PSUs that may be only 5-10% less efficient than at 50% loading). The bigger issue is pricing. Because it takes more/beefier components to output 750W than it does to output 350W, higher wattage PSUs cost more than lower wattage PSUs. If your system only draws 100W, why not spend that extra money on a (ie 80 Plus Gold) 350W PSU so that you're gaining even more efficiency (maybe >90% efficient vs 80% on the CX750) at your typical operating loads AND the internal components are higher quality.
Lastly. Don't forget how many OEM machines (Dell / HP) are out there running on low wattage, no-name PSUs for 10+ years without problems. Yes, failures happen and you can decrease your odds of a failure by buying high quality aftermarket PSUs, but nothing grants you immunity.
Main: i5-3570K, ASRock Z77 Pro4-M, MSI RX480 8G, 500GB Crucial BX100, 2 TB Samsung EcoGreen F4, 16GB 1600MHz G.Skill @1.25V, EVGA 550-G2, Silverstone PS07B
HTPC: A8-5600K, MSI FM2-A75IA-E53, 4TB Seagate SSHD, 8GB 1866MHz G.Skill, Crosley D-25 Case Mod