I am going to suggest an answer based on "Derech Derush," not intended to be taking literally. Since it was Hash-m Himself who took the rib away from Adam, Hash-m had to give the rib back personally in order to fulfil the Mitzvah of the Torah (Vayikra 5:23) that one must return a stolen item to its owner. However, all of Adam's descendants for all time did not actually have the rib stolen from them personally, but they still are missing something, which is why everyone needs a wife. So if somebody lost something but it was not stolen from him, it is his job to go looking for it!

Here is a different answer to this interesting question:

1) The main thing we have to understand is that for Adam, his rib was not considered as lost. What I mean is that Adam knew exactly who his intended wife was. After all, there was only one other woman in the world at the time! Perhaps we may say that Adam had an easy time finding his match. For everyone after Adam, it is much more difficult, because no one knows at the outset the identity of his proper Zivug. That is why he must go around looking for her.

2) Even if Hash-m would not have brought Chavah to Adam, Adam would have had no trouble finding her. As we know, Adam gave names to all of the living creatures in the world. He knew the entire animal kingdom. He certainly would recognize his own wife. Wherever in the world she would be, it would not have been difficult to find her, because Chazal say that Adam was such a great giant that the flesh of his heel was capable of blocking off sunlight to the world (Vayikra Rabah 20:2).

3) Since it had been already decided beyond any doubt who the correct Shiduch was for Adam, Hash-m did a Chesed for him by bringing him his wife. The Gemara in Berachos 61a tells us that we learn from here that it is a Mitzvah to be a "best man" for the Chasan and help bring him his wife at the wedding.

4) I once saw a nice idea in the book, "A Tzaddik in Our Time" (the biography of Rabbi Aryeh Levine, the Tzadik of Jerusalem). He explains why, in the Sheva Berachos said at a wedding, we make so much mention of Adam and Chavah in Gan Eden. The blessings are emphasizing that every couple should try to compare themselves to the first couple in the world. Unfortunately, it often happens that after a couple have been married for a while, they start thinking, "What would things have been like if I would have married somebody else that I met before I married my spouse?" This clearly is a very unwise attitude to adopt. We must emulate Adam and Chavah, who had no choice about whom to marry. Every couple nowadays should also learn to be like that. The husband and wife should think that his or her spouse is the only one in the world, and that his or her "bashert" is the only one that exists!

5) This is what we learn from Adam. Just as Adam had no doubt about where his lost rib was, everyone should be like that once he has found his match.

Kol Tuv,

Dovid Bloom