I've a MBP with OS X Yosemite & I want to remotely connect with other Macs over internet, primarily for troubleshooting purpose. I currently use TeamViewer but I'm not satisfied with it.
Did the other side have the 5900 port open? Every machine you want to connect using screen sharing must be in a network with this port open.
Did you tried Messages app feature to do it? You just need to select a contact, click on Details and Ask to Share Screen.
Once approved in the other side, you can see the other screen. And you can talk with the other side if you want.
To control the other screen, from the other side must select the connection icon and allow you to control it.
I used to have installed Team Viewer until I discover this functionality.