Summary
Not impossible. In fact pretty much looks like it. But there are holes in the story attached to it. Newspaper articles from the day that are still online do apparently not feature this "cut Mobutu's face out of the bills" particularly. But there is enough evidence for the existence of the bills and some circumstantial evidence lends support to their usage as bills in circulation, as well as some arguments from reason that stand for and against that.
"Cash shortage" seems to be used not quite in the right way here. Zaire and then the Democratic Republic of Congo had much too much cash, as the country suffered from a quite massive hyperinflation. Curiously, Wikipedia fails to list Zaire. But in that country the inflation rates were
1988 80%
1989 104%
1990 82%
1991 2254%
1992 4130%
1993 1987%
1994 23773%
1995 542%
1996 659%
1997 176%
In Zaire's case the rate of inflation was a few thousands of percent during the early 1990's then peaked at about 24 thousand percent in 1993-1994. Thereafter the rate dropped to a level of a few hundreds of percent. In Zaire's case a factor limiting the inflation of the money supply was the fact that it finally could not come up with hard currency payments to the company printing up the bank notes.
From 1987 when the IMF price level series began to 1997 the price level increased by a factor of 4.25 billion. That which cost 1.0 New Zaire in 1987 cost 4.25 billion New Zaires in 1997.
Thayer H Watkins, Emeritus Faculty, Economics, San Jose State University on Hyperinflation in Zaire
If we look at just the reports from all those years of civil war in the Congo from the Economist and focus on the very turbulent time 1997 (The hope for Zaire, The last days of Mobutu, Liberating Zaire is the easy bit) we can imagine the chaos that ensued. That was no simple change of government and the Kabila and his forces were not the most competent when it came to anything else but fighting and looting (collection of newspaper articles, mainly from South Africa: PDF, esp p 43 ("New banknotes to stop Zaire's economic rot", StarFoeign Service, 5 May 1997)).
One thing that continues to this day is that there is actually too much money around, and at the same time not enough money:
Exchange rates vary in different parts of the country. In Kinshasa, the franc trades at about 325 to the dollar; in the east, it is 240; in the area of northern Congo controlled by Jean-Pierre Bemba, a warlord, the rate is 220. Shopkeepers are suspicious of all banknotes anyway, because a previous government once counterfeited its own currency (the official printers printed two or more copies for each serial number, and various cronies kept the duplicates). Traders in the east will accept neither the pink 50-franc note, featuring a humble mud-hut, nor the blue 100-franc note, with its rather grander hydropower station. In the north, all denominations above 20 francs were barred by Mr Bemba, the warlord, until he made peace with the government this year and declared all Congolese notes legal tender in his fief. That includes a relic of the Mobutu era, the new zaire, a gorgeous pink currency, which still circulates in the north at a couple of million to the dollar.
Too many notes Exchange-rate arbitrage favours the brave, Economist, 2002
This situation was of course the same in 1997:
But the reach of the market women extends only so far. Those million-zaire notes they scoff at trade in Lubumbashi, the capital of Shaba province, at only 300,000 to the dollar. This, of course, has created opportunities for arbitrage. Money traders snap up unwanted prostates in Kinshasa, fly them to Lubumbashi and trade them for the smaller-denomination notes wanted in the capital. Even airline seats, though, are scarce in Zaire. The traders simply cannot move enough banknotes around to equalise the exchange rate.
Neither prostates nor the smaller 10,000 new zaire notes will get you far in the diamond-rich province of East Kasai. Here, traders prefer old zaires. The reason is simple enough: an abandoned currency should not experience inflation. Mysteriously, though, as grubby old notes wear out, new ones appear. Some say they are old stocks kept by banks. Others claim that new old zaires are being printed in South America. Whatever the case, old zaires trade at 16m to the dollar in East Kasai—and do not trade at all in Kinshasa or Lubumbashi.
If the rebels who have conquered eastern Zaire succeed in toppling Mr Mobutu's government, one of their first tasks will be to introduce yet another currency. This is certain to be tumultuous, because imposing a single exchange rate across the entire country will bring overnight price drops in some places and huge rises in others. A new currency will surely displease Kinshasa's market women as well—and reaffirm the old suspicion that the biggest obstacle to Africa's economic advance is Wall Street.
Popular monetarism, Economist 1997
What was Mobutu's legacy in 1997:
A dearth of state funds: government coffers and bank accounts were literally empty of money and precious gems, their contents smuggled out of the country in the days and weeks preceding the fall of Kinshasa.
Chaos at ministries: Ministry files had often been lost, destroyed, left in utter chaos or, in some cases, had never been maintained in the first place. Many ministry buildings were stripped of most or all furniture and equipment, forcing the new government to work out of the (costly) Hotel Intercontinental, which at least had a functioning fax machine.
Carole J. L. Collin: "Reconstructing the Congo", Review of African Political Economy, Vol. 24, No. 74, Africa's Environmental Crisis: Challenging the Orthodoxies (Dec., 1997), pp. 591-600.
A whole decade of hyperinflation and economic collapse and fracturing markets with a multitude of currencies diminish the role we expect from an official currency, and any reform that is attached to it during those events:
This problem had been temporarily resolved by issuing banknotes with a higher face value. However, by January 1993, this was no longer possible. The market women in Kinshasa refused to accept the newly issued 5 Mio Z-note as a means of payment, thereby expressing their loyalty towards the then Prime Minister Etienne Tshisekedi, who had called the new banknote illegal. Following this incident, the 5 Mio Z-note continued to be refused in Kinshasa, but was at the same time accepted as a means of payment in the interior, at a lower rate (1/5th of its face value). The refusal by Tshisekedi’s home region (the Kasai provinces) to replace the ‘old’ Zaire by the New Zaire did not constitute the only threat to the unity of the Zairian monetary zone. Indeed, the Zairian economy at the same time witnessed an increasing dollarisation of transactions, and, in some cases, the Zaire was being replaced by other African currencies or by European currencies. The last official monetary reform dated back to 30 June 1998, when the ‘old’ Zaire was replaced by the Franc Congolais. During the two Congo wars, the fragmentation of the Congolese economy continued and even markedly accelerated. On the monetary level, this resulted in a further decrease in the foreign currency reserves owned by the ‘Banque Centrale du Congo’ (BCC). Some of the new policy measures introduced by the Kabila government, after its take-over in May 1997, were particularly detrimental to the system. As Christian Dietrich explains, the ban on foreign currency, introduced in January 1999, was very harmful to the national diamond economy. Foreign diamond dealers were not pleased with the obligation to deposit all their foreign exchange in Congolese banks, for which they received an equal sum in the unstable local currency. Furthermore, due to the government’s habit of printing money to pay for its war effort, the value of the Congolese franc dropped steeply, while the difference between the official and parallel exchange rates increased.
Jeroen Cuvelier: "Linking the Local to the Global: Legal Pluralism in the DRC Conflict", p 197–216, in: Koen Vlassenroot & Timothy Raeymaekers (Eds): "Conflict and Social Transformation in Eastern DR Congo", Academia Press: Grent, 2004.
It is therefore not unimaginable that quite a few hole-punched bills were in circulation. Like this one:
Hole Punched Notes
In 1997, Zaire’s (now the Democratic Republic of the Congo) dictator Josepeh Sese Seko Mobutu was finally overthrown. As his face featured on the country’s bank notes, the new government simply punched out Mobutu’s face out of their existing currency and continued to use it until new currency could be printed.

Hole Punched Notes, UKcredit, MoneyLife, 2017
Trusting the above may not be easy, but at least these notes are still sold, in the west, at apparently much better prices than in in 1997:
(click to enlarge)
Price: $14.95
Description
WAS MOBUTU KUKU ? WITH HIS HEAD CUT OFF on SET of TWO
Mobutu Sese Seko Kuku also known as Joseph-Desiré Mobutu was the President / Dictator of the Democratic Republic of the Congo (renamed Zaire in 1971) from 1965 until his death in 1997. He was put into power primarily by the USA (mostly CIA) & Belgium and, in the process, gained an enormous fortune ($15 Billion) through blackmail, exploitation, embezzlement and corruption, leading many to call his rule a “ kleptocracy ”.
In 1997 there was a revolution lead by Laurent Kabila which ousted all vestiges of the Mobutu regime, including getting rid of his image from the money. Because of high inflation none of the money retained any value including these 5 & 10 Francs with Mobutu’s head cut out by some ticked off supporter of the new regime.
Set of 2 ( 5 & 10 Francs )
Quality; You will receive what is pictured or better.
Or a very respectable auction house:

Auction catalogue (past auction)
Lot Description My pre-bid Starting price
SINCONA Auction 45 - 26.10.2017 09:30
World Banknotes, Documents, Stocks & Bonds
BANKNOTEN | Verschiedene Länder | misc
Lot 7493
Lot USA. 2 Dollars (4) Blatt 1976, Replacement-Notes. & Zaire. 10 Zaires 1977, 27. Oktober. Portrait Mobutu ausgestanzt / cancelled.
Pick 461, 23b. IV - -I / Fine-about uncirculated.
Starting price
50 CHF
ca. 44 €
That disgruntled supporter of the new regime was probably Mwana Nanga Mawanpanga who was responsible when the regime change was taking place and the monetary system was in total limbo from May to July 1997 and when the new franc where agreed upon and finally introduced in 1998.
So it looks like these notes were punched in 1997 and not intended to be in circulation, just invalidated.
But then they were used, and apparently used until they fell apart.
Transcript: The portrait of Joseph Mobutu, the ex-dictator of Zaire, used to adorn every 20,000-zaire banknote. In 1997, Mobutu was overthrown and Zaire was renamed the Democratic Republic of Congo. Before a new currency could be designed, treasury officials had to use the old notes, so they simply punched Mobutu's face out of the bills.
Source Colors magazine: #85 Going to Market, 2012
There is only one problem to observe: the above picture shows a 20000 zaire bill from 1991:
P39a TBB B124a B-H 20,000 zaires 01/07/1991 UNC $ 3.30 In Stock
Printer: Hotel Des Monnaies-Zaire. Bank of Zaire on reverse. Mobutu Sese Seko on face and as watermark.Leopard.Solid security thread with printed Republique du Zaire. Signature: John Gualberto Nyembo Shabani.
But in 1997 the new zaire was officially the only valid currency:
P72S TBB B148as F-A 20,000 new zaires 30/01/1996 UNC $ 11.88 In Stock Specimen note. Signature: Patrice Djamboleka Loma. Printer: Giesecke & Devrient.- Munich.Holographic strip. Windowed security thread with demetalized Republique du Zaire. Mobutu Sese Seko on face and as watermark.Leopard.
Source Kate's paper money
From 1997–1998 the central bank did the following:
Inflation halted instantly and even turned into deflation for about six months, as the demand for domestic currency picked up (from May to October 1997, consumer prices fell by a cumulative 36 percent and the appreciation of the new zaïre against the U.S. dollar was of a similar magnitude). The new authorities prepared a comprehensive economic recovery program, including a monetary reform in which the new zaïre would be replaced by the Congo franc. In the run-up to the currency exchange, which took place successfully in August 1998 at a parity of NZ 100,000 = CF 1, the Central Bank used available stocks of money-printing paper to expand the supply of new zaïres. Although this involved some risks and led to somewhat higher inflation (a monthly average of 1.2 percent during the first half of 1998), it was needed to eliminate the overhang of illiquid bank reserves and thus establish parity between currency and bank deposits.
Footnote to the above paragraph: The issuance of “new” new zaïres gave rise to a singular situation, whereby banknotes of the same denomination but of different color schemes co-circulated at different exchange rates. Prior to the currency reform, exchange rates also differed among provinces, even for the same types of banknotes, because the new authorities had maintained tight restrictions on the movement of commodities and currencies across the country.
Philippe Beaugrand: "How the Congo Decomposed in the 1990s", p77, in: Ernesto Hernández-Catá (Ed): "The Africa Competitiveness Report", World Economic Forum: Geneva, 2004.
Conclusion
Those banknotes exist. Officially these bills were old and even older in 1997. They were invalidated by those holes and by inflation anyway. But in the chaotic situation with local war lords controlling parts of the country in a long civil war and corrupt regime members and the war lords flooding the markets with their stashes of old bills they remained in circulation. The "cash-shortage" and "new regime waiting for a new money design" parts of the story attached to it seem more like well narrated inventions. They make not much sense in the situation. Almost everyone had more than enough banknotes and the effort to collect old bills to cut out the face of the former dictator would be pure waste on nominally big notes that bought you very little to begin with. Unless you are far from the capital and declare those notes to be valuable. Or unless you take part in the second economy, the shadow markets which was three times the official one in those days. Or unless you take over a government and find it empty of official currency but stashes full of old money lying around