To recover deleted files, the phone had to be rooted by Dr, Phone. That could have left some residual files that make some apps think that the phone is still rooted. the only way to truly remove any traces of rooting is to reflash the stock ROM, but you have to back everything up first (see
Backing up an Android Device) because the stock ROM doesn't come with your pictures, music, etc.
Since it's a Samsung, though, flashing a stock ROM is trivial - see
[Samsung] How to flash Stock ROM via ODIN. You may die of boredom, but I've flashed a few hundred Samsung phones and never had a problem (as long as there was something else to do while it rebuilt the Dalvik cache).