Take the province, if the HRE demands it - declare war on them. If your neighbours get upset, attack them as well. Nothing like a good multi-front war. This is then a good excuse to take a few more provinces around your borders. Having thus demonstrated your superiority, ceasefires should be easily acquired - if these are not forthcoming, eliminate a faction or two to ram the point home.
Admittedly I'm a bit of a warmonger - so my advice may be a bit hawkish.