If they have not hung up on the call they deleted them on they can still recover them, if they have hung up the only way would be restore from a backup if they were saved that way. if the backup occurs only on sundays and a message was received and deleted on wednesday then the answer is no.
JohnThePhoneGuy
"If I can't fix it, it's not broke!