Você só vai conseguir recuperar as conversas se o histórico de Messenger já estava ativado: você tinha feito isso? Se afirmativo, você encontrará todo o histórico na caixa de conversa do contato. Fale com o contato, talvez ele tenha a conversa guardada no histórico dele. Veja mais detalhes nesta dica: Como recuperar as mensagens excluídas no Facebook
Caso contrário, e se você suprimiu a conversa pelo computador, você pode tentar recuperar com um software, tipo Recuva ou o Data Recovery.
E, sim, alguns serviço especializados propõem a recuperação de dados, como as conversas do Messenger. Não é garantido, mas vale a pena conversar com um técnico sobre esse tipo de recuperação, se for importante para você.