If you want to beat a dead horse: allow fb users to add people they like to your service whom aren't their friends using their URIs on fb. Use fb's ad api to allow users to pay for highly targeted ads to these people they like (<--monetize this). This will also help solve your chicken and egg problem. Where two anonymous users add each other's fb URI, there is a match and both are notified (you can crush crush notifier).
Bonus points if you can combine both these concepts into one service uniformly. This would be how I would make a dating service. Btw, nice domain name.