It really depends what song your using I suppose and why you would like to use them.
There are some singers who do not wish to have their songs reprinted to personally I would try to avoid using those singers covers. Others I suppose might be okay ( though once again, depending on what your using it for) as long as you give proper credit.
If your still not sure/if the singer seems vauge about their rules on their songs I would try to contact them and ask.
Well if they were covered by utaites that means the song doesn't belong to them; you'd have to contact the producer / the person who uploaded the original song on NND. Look for instrumental versions that they uploaded themselves; they allow you to use those in covers.