That type of double negation is pretty common in Spanish and it just reinforce the negation, like saying "I won't do that by any means". But I have to say that when you are writing or simply when you are at a formal environment is frowned upon, I wouldn't use it while spoken or writing a letter to a client, and will reduce it to one simple negation using something like this:
- Entonces tampoco existía solicitud alguna de mediación
And for the other examples using the first one possibility:
- Nunca iré a Japón
- Nunca me casaré contigo(more formal) / En la vida me casaré contigo(more informal but not so much, en la vida can be an informal expression in itself)
About the history, I can not be too much precise, I simply don't have the knowledge, but notice that double negation was used in the "castellano antiguo"(old Castillian) in medieval age. You can see it in many books and it seems I have been able to find a reference online speaking about all this: double negation google books.
Even though I don't know the referenced book nor the author, I've read books from that age in old castillian and they used double negations, so you can assure that it's at least older than the XVI century, and I can remember for sure that in the "Cantar del mio Cid" they used double negations too. That's about the XIII century.
So, yeah, pretty old.
PS: About a poem from "Cantar del mio Cid":
Conbidar le ien de grado, mas ninguno non osava:
el rey don Alfonsso tanto avie le grand saña.
Antes de la noche en Burgos dél entró su carta,
con gran recabdo e fuertemientre seellada:
que a mio Cid Roy Díaz que nadi nol diessen posada.
I thought I should translate that old Castillian to nowadays Spanish. I'll do it with the little I remember, so if someone feels like correcting it, go, and forget my poetry skills please ;)
Le invitarían de buen grado, pero ninguno no osaba:
tal era la saña que el rey don Alfonso le tenía.
Antes de caer la noche, a Burgos del rey llegó una carta,
a buen recaudo y bien cerrada:
que al mio Cid Roy Díaz nadie no le diese posada.
Notice that those double negations are not used nowadays, and are not correct nowadays, but they're in my opinion a clear signal of how older and common are that type of "constructions" in Spanish.