After reading some papers and searching in the corpus, I've rewritten the answer.
@EEG is right that "I find it unlikely that 不期然（“unexpcted") would be paired with 果真 (implies "expected") often enough to morph into a new phrase." Search in the corpus confirms it.
There are no hit of 果不期然, but the earliest 不其然 was used abundantly and first recorded the Spring Autumn Period. 《春秋》以德为怨，秦不其然。《论语》孔子曰：「才难，不其然乎？」From the Confucius quote, it's clear that 不其然 is 反诘 (rhetorical), which implies affirmatives.
果其然 also has some hits. The earliest is from （北宋）《新唐书》 君宝闻曰：“王者不死，果其然！”
It is much more probable that
“果(其)然”+ “不其然乎”类 → “果不(其)然”
You can read more in the paper 叶建军.“果不(其)然”的形成及其演变[J].中国语文,2016(02):192-201+255.
Some papers more or less hold that 果不然 is a merger of 果然 and 不出所料, and 果不其然 is a 增字四字格 from 果不然. (叶建军.“果不(其)然”的形成及其演变[J].中国语文,2016(02):192-201+255; 概念叠加与构式整合——肯定否定不对称的解释) I find this less convincing. 不出所料 is formally too far away.
But with either of the above two thoughts, 不 is a negative particle.
OLD ANSWER
About this word dictionaries all agree with each other.
中國大百科全書出版社《新編成語詞典》第293頁、人民日報出版社《中華詞典寶庫中華成語大詞典》第310頁 果 as 果真.
《新編成語詞典》、《中華詞典寶庫中華成語大詞典》、《新华成语大词典》gloss 然 as 这样.
《新編成語詞典》、《中華詞典寶庫中華成語大詞典》、江蘇教育出版社《漢語成語源流大辭典》 interpret 其 as a modal particle. Among them 《漢語成語源流大辭典》 says it's speculative.
None of them explained 不.
《漢語成語源流大辭典》gives a variation 果不期然. 期 is to expect. 不期然 is short for 不期然而然, which means 没有期待如此而竟然如此. It has the same meaning in 果不期然. 不期然而然 dates back to at least Song Dynasty, while 果不其然 is a Qing Dynasty coinage.
Hypothesis 1: It could be that 果不其然 is short for 果真+不期然（而然）. The speculative modal particle 其 is a grammatically weakened form of 期. If so, then 不 is indeed used as a negative particle.
Hypothesis 2: If 果不其然 and 不期然 are not related, then 不 is better interpreted as semantically void.
Other variations include 果不然 （现代汉语词典(第7版)）, 国不了然/果不溜然（胶辽官话《汉语方言大词典》）. So 其 is first-order optional （果不其然 > 果不然）, while 不 is second-order optional （果不其然 > 果不然 > 果然）. Note that here '>' is just an ad hoc symbol, not derivation; 果然 is way much older than the other two, dating back to at latest Warring State Period. This seems suggestive that at first 不 is not void and thus used as a negative particle （果不其然 > 果不然） but then becomes a meaningless particle （果不然 > 果然）.
In Chinese and other languages, there are indeed 冗余否定, like 好不热闹 means 好热闹. But this is not satisfactory as there's also another side. I don't know the term but it seems that a negative is missing, like 好容易 means 好不容易. I think we need a theory that can explain both scenarios at the same time.
In other structures, this phenomenon also exists. E.g. 《诗经》:王之荩臣，无念尔祖。（无念 means 念）徒御不驚，大庖不盈。（不驚 means 驚，不盈 means 盈）。Traditionally, here 不 is interpreted as 語助詞。無義。或用以足句，或表示語氣。（《辞源》）.
Sagart explains it as iambic. He thinks Old Chinese is not predominately monosyllabic. Words have iambic variations which put a weak and meaningless syllable before the root. One evidence he uses is 貍, *mə-rɨ, which has an alias in 《史记》 as 不来 *pə-rɨ. This type of iambic words are most commonly recorded as 不- or 无-. This is perhaps one source of the void usage of 不. Though the spoken language has in general long lost the weak leading syllable, the legacy use of 不 persists. So in 好不热闹 and 好容易, both 不's should perhaps be interpreted as a meaningless syllable; it doesn't determine the negativeness in this structure.
Personally, I think 果不其然 is short for 果真+不期然（而然）. So here 不 originally means negative. But then the even shorter form 果不然 by coincidence agrees with the void usage of 不 and the long-established word 果然. Therefore, these two usages of 不 has merged in 果不其然.
供不应求 and 得不偿失 have completely different structure: N1+不+V+N2. N1 cannot V-ing N2. N1 and N2 are verbs but used nominatively. This is common in East Asia languages, sometimes termed as verb nouns (the same form can be used either as a nominal or a verb). In this structure, 不 is always a negative. The roles of each character do not match those in 果不其然.
