We've found that the problem was a change with PayPal regarding standard checkout where shipping and/or sales tax was being charged, specific to the following locations:
'BE', 'FR', 'ES', 'DE', 'NL', 'IT', 'AT', 'PL', 'SK', 'BR', 'TR'
Fortunately our development team was able to implement a work around to resolve the problem for now. Since it is likely that PayPal might undo this change in the future we will continue to monitor the situation.