I would first check the rectifiers first, maybe a diode inside those rectifiers shorted or something like that, causing the rectifier packages to overheat and desolder themselves. Alternatively, maybe something shorted after the fuses but the current was not high enough to blow them.
If everything's OK, then yes you should consider adding heatsink to those rectifiers.
Look in the datasheet :
http://www.comchiptech.com/cms/UserFiles/KBPC10005-G%20Thru224770.%20KBPC5010-G%20Series%20RevA.pdfYour new rectifier is rated for 15A as long as the temperature stays below about 55c . Above 55c, with each degree, the rectifier will handle less current. I don't think those rectifiers are used for such high currents but you never know... Ideally, you would remove one fuse and put a multimeter there in series to measure how much current is going through the rectifier, just in case some part of your arcade draws too much power.
The tops of those rectifiers should be isolated (but check with continuity mode of your multimeter to be sure) so you should be able to just apply some thermal paste/adhesive and put some heatsinks on them.. Here's some suggestions:
http://www.digikey.com/product-detail/en/658-60AB/345-1072-ND/340365http://www.digikey.com/product-detail/en/658-60ABT1E/345-1108-ND/2643561It shouldn't be an issue to connect all three at one large heatsink. With higher temperature, usually the forward voltage of the diodes inside the rectifier goes down a bit which in turn would cause higher peak dc voltage out of the rectifiers but I doubt the designers of the arcade machine had temperature in mind when designing that, the output of that colder rectifier is probably regulated on some other board in the arcade machine.