I discovered that our issue was being caused by the XML being returned from the search. It contained an XML value on 2 lines instead of 1 which caused the %0A%0D to be added onto a link (specifically the <NextLink> value). Thunderstone has acknowledged this problem and said that a fix would be provided on the 21st.