Incredibly sharp swords are the obvious and any toys would probably have to be magical for them to be really fun (especially if they graft on), so I am kinda stumped.
Or how about giving them the option of bearing the other's child? For most couples that will bring them closer (though maybe not if they are both pregnant at the same time).
Thinking along the toys route, how about an (uncursed) girdle of femininity/masculinity? It would let Bern spice things up a bit for Maytag while keeping things monogamous.
I really doubt Bern would use a magical artifact like that
herself, since it isn't a life-or-death situation like the other times. However, since she hasn't objected to Maytag's outright flippant use of magic I don't see her objecting to something like this.
Depending on where Bern falls on the sexuality matrix it's likely that she wouldn't be all that enthusiastic about sex with 'Mantag'; Maytag is certainly close enough to Bern to know how it would turn out, and I think she'd be careful to choose something that Bern would be able to fully enjoy.
Maybe a "+6 Ring of Bigby's Protruding Phallus" and "Mervin's Belt of Potent Manbits"?
---
If we step away from blatant sexuality, Maytag could get them a matched pair of wedding bands which have been enchanted to allow them to both sense each other's location and condition, as well as communicate at any distance. Aside from the obvious meaning of receiving a wedding band as a gift, they would be practical and useful enough that Bern would almost certainly accept it. That's not even counting how much it would work towards their "No more secrets" goal.
It would be pretty close to an ideal gift, I think.