Maybe decoding 96700-Galer%EDa-de-im%E1genes as ISO 8859-15 and encoding it as UTF-8 before generating the permalink is a solution? Or are there actually incoming links out there that use the ISO 8859-15 encoded characters in the URL?
Mind, I’m not sure if it’s even necessary to use percent encoding for permalinks to work – I haven’t looked at the code. I guess you’ll need to experiment a little bit. I don’t think there’s an easy solution for this. If you find a solution, please post it here. It might be helpful for others.