Hmm this sounds like a iMessage problem but u guys did turn it OFF & signed out of iCloud. Have you tried switching the devices around to see if its still there? ( You taking the Note & she takes the iPhone & see?)
Have you guys deleted the contact name / number & see if that works?
Hmm Have you guys tried doing factory reset on the Note to see if that fixes? If no try that & see. My other opinion would be try logging back into iCloud via a iPhone with her account & turn it off again. See if that fixes it.