Oui, dans ce cas quel que soit le nombre choisi, on aboutit à peu près toujours à des ambiguïtés.
Ici, avec le singulier, on pourrait comprendre que vos grands-parents maternels et paternels partagent la même histoire, mais dans les faits ce cas est tellement peu probable que cette interprétation ne sera pas activée ou pas retenue.
Avec le pluriel, on pourrait comprendre qu’il ne s’agit pas de raconter leur(s) vie(s), mais leurs mésaventures, leurs magouilles. Là encore, ce n’est pas impossible, mais peu probables.

Bref, à vous de voir !

(En fait, si le racontez-moi leur(s) histoire(s) est précédé de « Racontez-moi la rencontre entre vos grands-parents paternels et celle entre vos grands-parents maternels », il n’y a plus vraiment d’ambiguïtés. Personnellement, je préfère la forme singulière, mais c’est très subjectif.)

Edit (après la réponse de CParlotte)

[En laissant de côté la question de la formule construction réfléchie qui me semble particulièrement inadéquate, et en supposant que CParlotte a en tête l’identité entre le sujet et les possesseurs plutôt que la réflexivité.]

Cette possibilité de choix entre le singulier et le pluriel n’est absolument pas limitée au cas où il y a identité entre le sujet et les possesseurs :

Ensuite, les cavaliers descendront de leur cheval / de leurs chevaux, et le palefrenier conduira leur cheval / leurs chevaux à l’écurie.
Ensuite, nous descendrons de notre cheval / de nos chevaux, et le palefrenier conduira notre cheval / nos chevaux à l’écurie.
Ensuite, vous descendrez de votre cheval / de vos chevaux, et le palefrenier conduira votre cheval / vos chevaux à l’écurie.

Et c’est vrai que parfois ça chiffonne un peu l’oreille, mais si je reprends l’exemple avec l’épouse et que je prends une « construction réfléchie », le singulier – qui est censément seulement possible dans ce contexte d’après CParlotte – me chiffonne l’oreille :
Nous viendrons avec notre épouse.