Must admit it does sound like a PSU problem but there are others to eliminate first.
First, remove and replace every connector they can work loose over time and lead (pun intended) to poor connections.
Remove and reseat your RAM and all expansion cards.
While you are in the case, check the interior, heatsinks and fans for dust build-up removing as required, after all, you are in there, might as well do some Spring cleaning at the same time.
See if that helps.