This is one of those Japanese double-negatives that's going to give you headaches if you try to translate it literally. Which isn't going to stop me from trying...
Basically, it breaks down to "It's not that I <b>don't</b> have the feeling that (...), which is just a more tentative way of saying "I have the feeling that (...)"
In other words, you can basically read it as 気がする without changing the basic meaning. You'll also see this (perhaps even more commonly?) as 気がしないでもない. As you mention, these expressions are common with 気がする, but you'll also see it with other phrases, 分かる (分からなくもない/分からないでもない; e.g. 気持ちは分からないでもないけど・・・) being one that comes readily to mind.
And just in case this clarification might help as well, the 「なんともだ」 is likely implying 「なんとも言えない」.
Hope this helps. (Also hoping that native speakers and/or more experienced learners won't hesitate to correct any misleading or blatantly incorrect information in the above.)