Thinking like an engineer, since soulmates are made when the souls are created, a good way to find them is to find out which souls were created at the same time. The next question is, what does "created" mean in this context. Does it mean initially sparked (I tend to doubt that)? Does it mean encoded in the Akashic Records (I think this the most likely)? Or does it mean something else, such as when a soul is associated with a player account?
Or perhaps the last is exactly when a soul is encoded in the Akashic Records? If so, then how does one prevent two souls owned by the same player from being soulmates? That eventuality would seem to foul up the whole system.
Getting back from the tangent (it had a specific intent), it would seem that the Soulmate Cafe could work by trying to line up the potential creation times of souls. That could involve players sharing information on account creation dates and such.
On the other hand (assuming I haven't already run out of hands), perhaps all souls are created procedurally, two at a time, whereby the pairings could be determined algorithmically (one's complement internal identifiers come to mind as an encoding). If this is the case, then the identifiers would need to be deeply internal, and never be casually revealed to players, to avoid exploitation.