Use ICQ. You can set it so they have to ask permission to add you to their buddy list. They can include a short message when they request to let you know who they are.