Commissario
Did you specifically switch off Find my iPhone? That doesn't get switched off during a reset for security purposes. Simply signing out of iCloud doesn't do it.Well I've just been to check with GAME and they checked for me (showing me the phone too) and I was signed out of iCloud on it.
Going to change my password just in case though.