When Rosh Chodesh falls on Shabbat, a special haftarah (Isaiah 66) is read.
However, in our fixed calendar certain months can never have Rosh Chodesh fall on Shabbat (Kislev, Sivan). For certain other months, the haftarah for Shabbat Rosh Chodesh is superseded by a different haftarah (Tishrei, Tevet, Adar (II), Nissan, Av).
Thus, the haftarah for Shabbat Rosh Chodesh can only be read for the months of Marcheshvan, Shevat, Adar I, Iyar, Tammuz, Elul.
(I’m aware that there are differing customs regarding Av and Elul; for the purposes of this question assume a community following the custom I have outlined here.)
My question is, what is the longest possible interval in the fixed calendar between readings of this haftarah?
We last read this haftarah in Iyar 5780, and will not do so again until Elul 5782, a gap of 29 months. Is that the longest possible interval?
Bonus: what's the longest interval between readings of the haftarah of Erev Rosh Chodesh?