Yes, the user you want to send the coins to would need to have the app installed on his phone as well.
I don't understand the logic behind this. Why would you limit the user base only to those who have your wallet installed. If I as a user, wanted to send to an exchange, I wouldn't be able to do that?
Why would I want to use your wallet that asks for my name and phone number, when I can use other wallets that don't?