It sounds like the search you're doing is only of your Sent folder, but I don't know if that's possible in AOL's webmail.
Try this maybe: In the search box, click the drop-down arrow and try searching for something other than "Mail." Try to/from and put your name (or your friend's name) in the search box. Or try searching a subject that you know friends have replied to.