the water dunking is a surefire way of finding a leak of any size. if it is a large leak, you should be able to find it with a starsan solution in a spray bottle.
i would say to check for leaks at the normal serving pressure, as well as the highest pressure the keg will see (for me, it is around 50 or so because i leave some stuff at room temp while carbonated). it may be a small chance, but some things may leak due to not seating at a lower pressure, or conversly at a higher pressure because it exacerbates a stress already on the keg. i think both pressures would be good to check.
if you have a lot of time, you can do an overnight (or 24 hr) test just as a yes/no test. if you are doing a lot of empty kegs, i would just put 10 psi in each keg, and the next morning/day, pull the pressure release. if no pressure, you know for sure you have a leak. if the pressure coming out is fairly solid, and consistent among many of the kegs, they should be ok, but you can do a dunk test just to make sure, or star san - but if the leak is slow enough to still hold 10 psi over a full day, it will be really small, and you will need to dunk it to see the leak.
as a general rule of thumb, whenever i get a keg, i break it down, and replace all the gaskets except the lid, unless the rubber is brittle, then i'll replace it, check the poppets, lube everything up, and then pressure test. this works well for the majority of kegs that i have.