This dictionary states that a clause like 「申し訳なく思っていますが〜」 means "Though I was sorry—" What I don't understand is the usage of 思う here. 申し訳ない itself means "sorry," does it not? What does adding 思う do? How does that sentence differ from 「申し訳ないが〜」?
The difference between 申し訳ない and 申し訳なく思う is akin to the difference between "I am sorry" and "I feel sorry" in English, i.e. there is no essential difference.
In th example you have chosen, I believe, adding 思う in Japanese makes the phrase more subjective, allowing adding a contrasting feeling or view in a subordinate clause ("though"). For example if you were explaining the situation to a third person.
申し訳ないが in comparison would be more apologetic.
思う has a broader usage than a typical "to think" interpretation. See this question.