Just in case this helps some one else, I did manage to resolve the problem.
It seems that Paypal was checking the invoice number generated by the shop and saying that it had already been paid. Our shop had been completely rebuilt recently so I guess the invoice number had just started to coincide with old ones from the previous shop which had, indeed, been paid. I had no idea Paypal would check this.
The best answer would have been to change the format of the invoices in Hikashop but you can only do this in a commercial version (we are using Starter).
So, the only answer is to turn off this function in Paypal which is really difficult to find but it's somewhere in Profile > Payments > Login with Paypal (whatever that means) > Profile > My Selling Preferences > Block Payments > second option down "Block accidental payments" change to "No, allow multiple payments per invoice ID".
Now it works.