In theory a receiving User Agent can challenge any request including a BYE. In addition any Stateful Proxy along the request path can also challenge the request. In both cases the client must re-submit the request with its credentials.
There's nothing I could find in the SIP RFC that deals specifically with authorisation of BYE requests but this quote from "12.2.2 UAS Behavior" does indicate that in-dialog requests do need to support authorisation:
If a proxy challenges a request generated by the UAC, the UAC has to resubmit the request with credentials. The resubmitted request will have a new CSeq number. The UAS will never see the first request, and thus, it will notice a gap in the CSeq number space. Such a gap does not represent any error condition.
That being said it's very unusual for a BYE request to be challenged and I suspect there are a lot of SIP stacks around that would not handle it correctly. As Frank has intimated I'd be inclined to check the request routing by looking at the Record-Route headers on the OK response and make sure you are sending the BYE to the correct destination.