As has been accurately stated several times in this thread already, this behaviour is definitely, 100% due to songs in your iTunes library that have metadata that associates them with other Apple IDs.
Music from iTunes does not have DRM, so there’s nothing preventing anyone from sharing songs purchased through iTunes. But if any of those songs get into your library somehow (usually through piracy), Apple will ask for the password to those Apple IDs whenever you restore the phone.
But it doesn’t matter; it won’t delete the songs, and it won’t care if you don’t enter the correct password. Just keep hitting cancel until it stops asking, and go about your life. Do not erase and restore your phone; it’s a waste of time and you’ll just have to dismiss those weird Apple IDs again anyway.
If you want to actually solve this problem, you will need to comb through your iTunes music and scrub the iTunes account metadata off the songs in question. You will have to Google around to figure out how to do that.
But people need to stop thinking this behaviour means a new or refurbished phone has a virus, or is previously used, or hacked, or anything. Just hit cancel and live your life!