Tanto poderá utilizar uma construção como a outra. A construção abonada pelos nossos escritores na Grande Enciclopédia Portuguesa e Brasileira é a do complemento directo sem preposição. No entanto, utiliza-se também "desfrutar de", como exemplificado no dicionário Novo Aurélio Século XXI: "Desfruta de bom conceito no meio científico."

Quando ao facto de tratar-se de pleonasmo, não estou a ver por que motivo. Este verbo não é formado pela preposição "de", mas pelo prefixo "des", que me parece ter aqui um valor de intensidade.