does replace mean irretrievable?

At the end of a conversation on msngr today a box appeared saying that my msg
history with this contact was to large and would i like to save it to archive
or replace it..
in my hurry to sign off i hit the replace button and deleated nearly all
past conversation history with this contact.. i use xp professional as my os
and have not turned off my computer.. (someone told me this might make a
difference) .. so my question is.. does replace in xp mean irretrievable, did
i overwrite this infomation or is it possible to use some kind of data
recovery program?
i know this seems trivial but its not. please help.
.