Messenger doesn’‘t support searching users via clients or the Jabber user directory service. So you should receive errors when trying to conduct user searches using Exodus. (Technically, Exodus should disable that feature when connecting with Messenger since we don’'t list it as an active service.)
In any case, you cannot add users to your contact list by searching (in XMPP it’‘s called a ‘‘roster’’). Instead you must know their address using other communication channels (e.g. the same way you learn someone’'s email address: you ask them in person, on the phone, get it on a business card, etc). Once you know their address, add them using their address. In Exodus you do this by clicking on the plus symbol of the toolbar and entering the form information (which includes their all-important address).