The notice arrived in an envelope stamped “important information,” telling Kristin Fortner she needed to prove that she and her husband still deserved Medicaid. She filled out the form within a week of receiving it this past winter and mailed it back. So she was perplexed by a phone call almost three months later from the Arkansas Department of Human Services alerting her that she had neglected to renew the couple’s Medicaid and, unless she sent the paperwork, their health insurance would end.

Fortner quickly resubmitted the same form, this time in person. Except Arkansas already had cut them off. She discovered in May that her insurance had vanished as she tried to pick up a prescription for Suboxone, the medicine that helps her stay off opioids, from a Walgreens near her Fayetteville, Ark., home. Suddenly, she owed $380. Her Medicaid coverage, the pharmacy’s records showed, had expired April 30.

A 33-year-old waitress earning $3 an hour plus tips, Fortner walked out of the drugstore without the pills. She is among nearly 4 million Americans who have been lopped off Medicaid since the end of a pandemic-era promise that people with the safety-net health coverage could keep it, requiring every state to begin a herculean undertaking of sorting out who still belonged on the rolls. The 3.8 million — the most thorough tally — is an undercount, reflecting only people who have lost coverage so far in 38 states that have voluntarily made public their data from this sorting process, known as the Medicaid unwinding.

Most of those people have been dropped from Medicaid for reasons unrelated to whether they actually are eligible for the coverage, according to KFF, a health-policy organization, which has been compiling this data. Three-fourths have been removed because of bureaucratic factors. Such “procedural” cutoffs — prompted by renewal notices not arriving at the right addresses, beneficiaries not understanding the notices, or an assortment of state agencies’ mistakes and logjams — were a peril against which federal health officials had cautioned for many months as they coached states in advance on how best to carry out the unwinding.

Fortner’s experience attests to the bureaucratic maze ensnaring some people — and the damage being done to their well-being. The Arkansas Medicaid agency, one of the nation’s first to launch the unwinding, has repeatedly insisted that Fortner needs to provide different documents. Her husband, Ryan, has stopped making physical therapy appointments for a herniated disk. As for her Suboxone, Fortner felt like she was going through withdrawal when she skipped it for two weeks, and now, after paying for a partial order with a drug discount card, stretches the supply by cutting the pills in half.

Medicaid, the country’s largest public insurance program, is a legacy of the 1960s’ War on Poverty. The federal government provides most of the money, lays down basic rules and supervises states, which set eligibility standards and handle applications and renewals.

Beneficiaries typically must renew Medicaid every year, but that stopped in 2020 when the coronavirus arrived. With no one leaving the program, the number of Americans on Medicaid swelled to 85 million by this April, when the unwinding began in phases, with five states starting to terminate people. By July, every state except one had started removing some people from the program. Oregon will begin removing people in the fall. The government wants states to spread the undertaking over a year, although a few have chosen to do it faster — none more rapidly than Arkansas.

Health and Human Services Secretary Xavier Becerra has made clear his displeasure with the high rates at which low-income people are being severed from Medicaid without knowing whether they still qualify.

“[I]t is critically important to ensure that individuals do not lose coverage due solely to administrative processes,” Becerra admonished in a June letter to the nation’s governors in which he urged states to improve their renewal methods.

Some health-policy advocates and Democrats on Capitol Hill contend that HHS is partly to blame, saying federal health officials should exert a heavier hand with states that have been performing poorly.

“They have to be more assertive,” said Rep. Frank Pallone Jr. (N.J.), the top Democrat on the House Energy and Commerce Committee, which oversees Medicaid. Pallone said in an interview that the Centers for Medicare and Medicaid Services should explore whether some Republican-led states are deliberately winnowing their Medicaid rolls so they will have fewer low-income people to insure. Last year, Congress gave CMS the power to order states to draft plans to correct the problem and pause removing beneficiaries for procedural reasons — and to fine states that persist in mishandling cases.

During the unwinding’s first few months, CMS refused to disclose how many states were violating federal guidelines and how often federal officials were intervening.

In recent days, the agency has pivoted, portraying itself as stepping in when it discovers that a state is performing badly. According to Daniel Tsai, CMS’s Medicaid director, the agency has ordered a half-dozen states he did not identify to pause the removal of people for paperwork reasons and to reinstate some whose coverage had been denied — up to tens of thousands of people, depending on the state. The agency is conferring with about a dozen other states regarding potential violations.

Tsai said some states are failing to follow a federal requirement that they rely when possible on electronic data — such as wage records from food stamps or other benefits programs — to check people’s eligibility automatically and avoid the burden of renewal notices.

“Make no mistake, where we have found problems or violations of federal requirements, we are taking action to ensure that states correct the issue immediately,” CMS Administrator Chiquita Brooks-LaSure said during a recent news briefing.

CMS has been collecting states’ unwinding data monthly but said it could not release its first state-by-state snapshot before the end of July because federal officials needed time to check the accuracy of that data. Many health-care advocates say CMS should have been providing this unwinding picture sooner.

On Friday, the agency issued the first official unwinding data based on 18 states that began the process relatively early. The report evaluated what happened with 2.2 million beneficiaries whose status was scheduled to be reviewed. It found that 46 percent remained on Medicaid or the Children’s Health Insurance Program, 32 percent were removed from the program, and 22 percent of the reviews had not been completed. Of those removed, 79 percent were for procedural reasons.

Spanning just two months, the federal snapshot is less complete than the data compiled by KFF and separate tracking of 20 states by Georgetown University’s Center for Children and Families. Still, all three sources show considerable variation in how many people have been cut off — and the rate at which people lose coverage for paperwork reasons. Michigan and Pennsylvania are doing comparatively well, with most beneficiaries who have come up for renewal remaining on Medicaid. The KFF and Georgetown tallies show that, in both states, 3 in 5 cases removed from the rolls were dropped because of ineligibility.

Florida has severed the second-most people, after Texas — slightly more than 300,000, two-thirds for procedural reasons. And CMS says Florida has been the only state unwilling to discuss with the agency how to minimize removing people for the wrong reasons.

“We are alarmed by the data,” a coalition of more than 50 health-care and other advocacy groups wrote this spring to Florida Gov. Ron DeSantis (R), calling on the governor to pause the unwinding until the state improved its methods.

Rep. Kathy Castor (D-Fla.) and the seven other Democrats in the state’s congressional delegation also wrote to DeSantis, saying the disenrollment rate “is incredibly concerning” and echoing the call for a pause. “I’m very concerned too many Floridians are going to be lost in the shuffle,” Castor said in an interview.

According to Castor’s staff, DeSantis, a candidate for the 2024 GOP presidential nomination, did not reply to the lawmakers’ letter. The governor’s office referred questions from The Washington Post to the Florida Department of Children and Families. Mallory McManus, the department’s deputy chief of staff, said the agency had developed “a thoughtful, common-sense plan … to return to normal Medicaid processes” and already uses some procedures urged by federal health officials.

Florida’s top priority is ensuring that those who are eligible for Medicaid remain enrolled,” McManus said by email.

Already, the large proportion of beneficiaries in some states tumbling into the ranks of the uninsured is starting to hurt clinics and hospitals that focus on low-income patients — especially in the poorest states, such as West Virginia, where about 1 in 3 residents have relied on Medicaid.

“It’s a total failure, this unwinding,” said Craig Robinson, the executive director of Cabin Creek Health Systems, a network of a half-dozen clinics in West Virginia. Every day, he said, people arrive for appointments or for medicine at each clinic, unaware that their Medicaid coverage has stopped.

Cabin Creek is not alone. At West Virginia Health Right, a Charleston clinic with 43,000 patients at three sites, the number covered by Medicaid fell by about 1,600 in May and June, the first two months of that state’s unwinding, according to Angie Settle, the clinics’ chief executive. The number of uninsured patients, usually fairly stable, rose by about the same number during those two months.

Settle said the unwinding is putting a strain on the staff as new people show up for medical services they can no longer afford — and a strain on finances as more people show up for medications for which no one else is paying the costs.

One of Health Right’s new patients is Heather Elkins, who lives nearby with her daughter in Dunbar, at a bend in the Kanawha River. Living on $1,100-a-month Social Security checks, Elkins, 63, had no health insurance starting in 2012, when she quit the construction work that was hurting her body, partly because of breathing lime dust on river barges. Five years later, her health deteriorating, she applied for Medicaid, which has paid for medications for her high blood pressure, high cholesterol, depression and diseased lungs.

When she went to pick up prescriptions the first week in May, Elkins said, the pharmacist told her, “Honey, you’re declined. You don’t have coverage.”

She paid out of pocket for the prescriptions, except for the Symbicort to treat her chronic obstructive pulmonary disease, because a month’s supply would have cost about $400. Instead, she headed to Health Right for it.

Elkins said she isn’t certain whether her renewal notice from the West Virginia Department of Health and Human Resources never came or was stuck in the middle of other pieces of mail. She stopped at a state office to try to find out what she needed to do. Over the next two months, she was told to bring a Social Security card, assured that would suffice, then was told she would need to start a new application. When Elkins finally brought in the completed paperwork, an employee looked in the computer, ripped up the form without examining it and said she was back on Medicaid. Stunned, Elkins asked about what she’d been told by the first worker who triggered the whole runaround — and was told he had been a new employee and did not work there any more.

According to Sarah Young, the health department’s deputy commissioner, each beneficiary receives three phone calls and written notices before a case is closed. She did not address how situations such as Elkins’ could happen but said by email, “the challenge remains how to increase the number of individuals who submit their renewal forms in a timely manner to prevent a loss of coverage.”

Some states face special obstacles. In Alaska, renewal notices do not always reach intended recipients in rural communities that lack roads or broadband internet, according to Anne Zink, the state’s chief medical officer. Some towns and villages at times lack a working postmaster, so mailbags containing the notices sometimes pile up outside shuttered post offices, Zink said.

Alaska is among 34 states, plus D.C., that have been out of compliance with at least one federal requirement for how to conduct the unwinding, a CMS tally shows. But even some states that meet all the federal rules have high rates of people being dropped from the program for paperwork reasons, mystifying state officials and patient advocates alike.

One of those states is Indiana, where 86 percent of removals were done on procedural grounds, according to the KFF and Georgetown data. In addition to sending beneficiaries a postcard, letter, renewal packet, text messages and phone calls, the state’s Medicaid agency is launching a multilingual ad campaign and has collaborated with food banks, pharmacists, clinics, school systems and child-welfare workers to spread the word, according to Michele Holtkamp, the agency’s spokeswoman.

In Arkansas, a 2021 law requires the state to sort through renewals within six months, half the time the Biden administration recommends. Gov. Sarah Huckabee Sanders (R) published an op-ed in the Wall Street Journal in May saying, “I’m proud Arkansas is leading the nation in getting back to normal.” Most Arkansans who lost jobs during the pandemic are working again, she wrote, saying, “It’s time to get them off the path of dependency.” The governor did not say how many of the reemployed have health benefits through their jobs.

Trevor Hawkins, an attorney at Legal Aid of Arkansas, said some people have been told their Medicaid cases were closed at their own request — when that was not true. As in a number of states, he said, children are being removed from coverage if their parents become ineligible, even though the children still qualify. And some people are simply being denied and told to reapply, Hawkins said, so they are uninsured while “they are just patiently waiting to be reapproved …[with] no idea how long the line is.”

Arkansas Community Organizations, a grass-roots antipoverty group, held a protest last month outside one of the Department of Human Services’ Little Rock offices. Demonstrators carried hand-lettered placards saying, “Fix the glitch!” and “This update is life or death,” and one protester staged a skit simulating depositing information into a cardboard computer and receiving a slip of paper saying, “Denied.”

Gavin Lesnick, spokesman for the state’s human services department, said Arkansas is following “a detailed plan … that is both fair and helps protect Medicaid resources for those who truly need it.” He said that just because a case is closed for a procedural reason does not necessarily mean someone failed to receive a renewal packet or did not know about the unwinding. Some people, Lesnick said, have chosen not to return renewal forms, aware that they are no longer eligible.

In Fayetteville, Fortner does not know when — or if — her Medicaid coverage will be restored. She does not understand why her 15-year-old daughter has been allowed to stay on the children’s version of Medicaid, while she and her husband, the manager of a vape shop, were cut off — without receiving a denial letter.

She takes Suboxone to stay clean from the opioid addiction she said she has struggled with since she was 14 and prescribed painkillers for whiplash from a car crash. The day this spring she could not afford the Suboxone, she said, “I felt hopeless … and pretty irritated.”

After discovering in May that her Medicaid coverage had been cut off, she went to a local branch of the human services department to find out what was going on. “I was told I would need to reapply completely,” Fortner said. By the end of that week, she took in all the requested information, including proof of her husband’s previous jobs and his current one.

“They said I was good to go,” she said, and was told the paperwork would take 30 to 45 days to process. After calling repeatedly, she returned in person in mid-June. She was told she needed to furnish evidence that she no longer worked at another waitress job she had left nearly a year before. She also was told her husband’s doctor needed to provide proof of why he was on Social Security disability. Her husband has never been on disability. She asked for a copy of the form with the disability question, but the employee said she couldn’t print it out because it had just been mailed to their home and, once it arrived, she could mail it back saying he did not have disability benefits.

“It’s very, very frustrating,” Fortner said. “I keep thinking I’ve done everything I’m supposed to do and it’s fine, but then, when I check, it’s not fine.”