ToxMe[1] seems to attempt to solve this issue by creating a public databases of emails and Tox IDs, though this defeats the object of the service being anonymous.

[1] https://toxme.io/