Hm, I'm rather surprised by the fact they are hosting mail servers with OVH. Most OVH servers are on several blacklists and OVH do not tend to take very kindly to people using email through their servers.
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.