ok, whoever stumbles on this thread, found the solution.
in my script above I used the method
([URI]::EscapeUriString($response.next_page_link))
to encode the string. Turns out this is not sufficient. Instead use this method to encode the string. I corrected my script above, works now like a charm.
[System.Web.HttpUtility]::UrlEncode($response.next_page_link)