The Memory Tree is their current god? I would posit then, any lesser deity related to the mind or memories would probably be acceptable. The best solution would of course be to check with his current deity, or some intermediary between him and his god. Depending on if the Memory Tree feels that the Beetle of Mislaid Memories is stepping on his toes, or just representing another aspect of memories.
Maybe the cleric could convince the Beetle to become a follower of the Tree. What better worshiper than a subservient god?
As far as what would that gain him? I'd give him the other domain, if another memory-related deity even has another domain. There are certain times when gaining domains is nothing but a power grab. This doesn't sound like one of those times.
There are several instances in D&D where worshiping multiple gods is fitting, and in real-world history. Depending on what you wanted. Aries never handled crops, and Demeter didn't handle the Sun. There are certainly some gods who try to be "all gods" and encompass everything, but the whole reason D&D deities even have domains is because none of them represent everything. They all represent a few related aspects of the world, and leave the other aspects to other gods.
Oh, and I generally wouldn't have him multiclass two different types of clerics. It'd be redundant and silly.