After weeks of tumult and parliamentary maneuvering—including Gov. David Paterson’s threat of a government shutdown that would bring “unimaginable chaos” and “anarchy in the streets”—New York finally has a state budget for the fiscal year that began April 1.

But the nearly $136 billion budget approved this week by the New York legislature is only tenuously balanced, even assuming a pending $828 million revenue bill is passed by the state Senate. Indeed, Mr. Paterson is already threatening to drag lawmakers back to Albany in the fall to deal with what he fears will be yet another midyear deficit.

The state’s budget travails are a case study in the pernicious impact of federal stimulus aid. The “fiscal relief” for states in last year’s $862 billion stimulus bill was supposed to minimize spending cuts and tax hikes. In New York it has succeeded only on the first count while failing miserably on the second and postponing the day of reckoning for the state’s overextended finances.

State spending in New York has continued rising despite the recession. The Legislature is a step away from having increased state taxes and fees by more than $9 billion in the last two years—including a state income tax hike of up to 31% on high earners.

The revenue bill in the state Senate has a slew of levies, including higher taxes on clothing, and retailers’ credit cards. It would boost New York City’s resident income tax by another 6% for high-income households and further curtail the deductibility of charitable contributions.

Businesses would effectively be forced into making an interest-free loan of $2 billion to the state over the next three years through the deferral of tax credits they’d previously earned for investing capital and creating jobs in New York. Mr. Paterson and the legislature also agreed to tax the carried-interest income of nonresident partners in New York-based hedge funds—a move Mayor Michael Bloomberg called “the best thing that ever happened to Connecticut.”

Bottom line: Two years after the financial crisis blew a Wall Street-sized hole in the state’s revenues, Albany has yet to get its fiscal house in order. Lt. Gov. Richard Ravitch estimates the state’s “structural budget” gap—the difference, adjusting for economic cycles, between recurring expenses and recurring revenues—at $13 billion, or roughly 15% of state-funded expenditures. A gap this large will never be closed without the kind of major structural reforms that federal stimulus aid has helped to forestall. The prime reform target must be Medicaid.

New York’s total annual Medicaid spending, $52 billion, is 73% more than the national average per enrollee—more than Texas, Florida and North Carolina combined. The federal government covers 50% of the cost. Since New York spends so much, however, it’s been rewarded by Obama’s direct stimulus aid to state budgets—specifically through a temporarily enhanced Federal Medicaid Assistance Percentage (FMAP), which has boosted New York’s federal match to just over 56%.

In February, President Obama’s 2011 budget proposed a six-month, $28 billion extension of enhanced FMAP funding—on top of the $90 billion from last year’s stimulus bill. Mr. Paterson immediately plugged New York state’s $1.1 billion share of the added money into his 2010-11 fiscal plan. Then, spooked by the rising national outcry over federal spending, the House of Representatives removed the added Medicaid money from its version of a broader “jobs bill.” Enhanced FMAP funds are also stalled in the U.S Senate.

Earlier this week Mr. Paterson joined other governors in Washington to beg for more FMAP, but he’s also called on the legislature to provide him with a “contingency plan” to cover a $1 billion hole if the FMAP funds don’t materialize.

Nothing doing, said Assembly Speaker Sheldon Silver, the most powerful Democrat in Albany. “If we would show the federal government that we don’t need the money . . . we can kiss that money goodbye,” Mr. Silver explained after passing the budget this week.

On Wednesday the state Senate’s Democratic majority hinted it was more willing to talk about a contingency plan before clearing out for the July 4 weekend. However, neither the governor nor the legislature has shown any appetite for anything close to $1 billion more in spending cuts.

As Lt. Gov. Ravitch wisely noted in January in these pages, much of the federal government’s recession “relief” has come with strings attached that actually make it harder for states to cut spending on health care, transportation or education. “The federal stimulus has led states to increase overall spending in these core areas,” wrote Mr. Ravitch, “which in effect has only raised the height of the cliff from which state spending will fall if stimulus funds evaporate.”

With an assist from the Obama administration, New York’s cliff just got even higher.