We actually managed to get things working. The trick was to "sanitize" our created pages' paths.
Before we had paths with non-ascii characters like: "/koskâvuotâ/ohtsâškoodán-päikkikuávlu-mun-tiäđám",
which were changed to: "/koskavuota/ohtsaskoodan-paikkikuavlu-mun-tiadam".
After that the deploys started working.
I can still open a support ticket if you want to investigate this further?