If someone is claiming they didn't add your photo to their contacts, perhaps they have you on Facebook and automatic sync with Facebook turned on?
If what you want is to give them a photo you could save your info as a contact, and just share the contact with them via a message?