Out of curiosity: why wouldn't Replenish work? Is it the whole "you choose timestamps" thing?
Would Crown of the Ages work?
If they are both comming into play via replenish, they can't chose the other to enchant, as you can only chose to move them to a permanent in play.
Crown of the Ages won't work since it only moves Enchantments to other creatures. You couldn't get them to enchant each other since they aren't creatures. If they were somehow made into creatures, then they couldn't enchant anything and would be put into the graveyard.
A couple of Aura Grafts could do it.