Carl,
From what you have written I see what you mean about how one defines native, especially going back to Roman introductions which can be misrepresented by many as native.
However, if the RHS, possibly the foremost source on plant and gardening related matters in the country (not necessarily history though) term it as native, that seems pretty good to me. I've also found lists of various plants the Romans introduced to the UK and can't find any reference to gorse?
However as I said, and hopefully the smiley shows, I'd rather learn something new than blindly fight a corner. So please do the further research and let us know.
Cheers,
James