After opening a ticket as suggested by PayPal_Patrick the problem was that I was adding the callbackversion in the wrong place. The full response to reject a shipping address on callback is:
METHOD=CallbackResponse&NO_SHIPPING_OPTION_DETAILS=1&CALLBACKVERSION=61