I believe Facebook recommendations are somewhat bidirectional - if they visited your Facebook page (by searching you, even if they didn't add you), I think Facebook will recommend that you add them.