They seemed to have some of the most secure jobs in Russia, working in the "power ministries" favored by President Vladimir Putin, himself a former KGB spy.
But firefighters, police officers and, according to some media reports, spies are now being squeezed by Russia's economic crisis, losing jobs and perks as the Finance Ministry cuts spending to build up resources for what could be years of Western sanctions.
For workers who specialized early to take up what were seen as jobs for life, the cuts at the Emergencies Ministry, Interior Ministry and Federal Security Service, a successor to the Soviet-era KGB, have taken many by surprise.
Even more so when they touch support staff for the army, seemingly untouchable when Putin excluded defense spending from budget cuts needed to weather the crisis, deepened by falling oil prices and the sanctions over the Ukraine war.
The cuts strike at the core of one of Putin's largest support bases, a sprawling bureaucracy of thousands of state workers who are generously funded and who make up a large part of Russia's ill-defined middle class.
A worker at the Emergencies Ministry, which groups together Russia's fire brigade, civil defense troops and the country's search and rescue service, said her team had expected a pay rise when they were called into a meeting this month.
Instead they were told of cuts at their firefighting unit attached to an armed forces base in southern Russia.
"We were told there was no money ... We didn't get any kind of clear explanation. The order came. And they didn't even let us see it," said the worker, who spoke on condition of anonymity for fear of retribution.
"Of course, it upsets me that the sackings happened in the military units because the regional head wrote clearly that the cuts would not affect the military parts. We just do not know the truth."
The worker said the cuts seemed random, not just targeting staff nearing pensionable age, but also experienced drivers, foremen and radio operators, who are mostly women aged 35 and above. Most will struggle to get other jobs.
"This is all happening at a very difficult time with an unstable economic situation in the country," the worker said.
Two days after reporting this, the worker said the job cuts had been suspended, but had no other details.
The Emergencies Ministry did not reply to a request for comment.
Reports in newspapers and across Russia's social media sites of mounting job cuts in not only the state but also the private sector have raised fears of rising unemployment at a time when the economy is heading for recession and inflation is rising.
Unemployment reached 5.5 percent of the workforce in January and the Economy Ministry expects it to rise to 6 percent this year — a small expected increase but one which is making some question the worth of the government's 2.34 trillion rubles ($38 billion) anti-crisis program.
With some police and drug squad officials saying they must cut costs by at least 10 percent, Alexander Rybolovlev, a state employee from the northwestern city of Arkhangelsk, took to VKontakte, Russia's biggest social networking site, to lament the crisis.
"They are cutting jobs in all services, the Interior Ministry, the prison service and the Emergencies Ministry," he wrote. "People are losing their jobs ... and they all have loans, mortgages. Soon they will take to the streets."
What is not clear is how deep the cuts will go.
Local media suggest ministries have been told to reduce costs by 10 percent, not necessarily through shedding jobs. Some have decided to curb perks such as hardship benefits.
The Interior Ministry, FSB, and Prosecutor General's office did not respond to requests for comment.
In January, Finance Minister Anton Siluanov said all budget expenditure should be cut by 10 percent, except social spending and defense, a priority for Putin who sees restoring Russia's military might as one of his main goals.
Just last month, Siluanov said Russia needed to cut its budget by an additional 600 billion rubles this year. According to Russia's RBC Daily newspaper that sum has already been reduced to 427.2 billion.
Even the Defence Ministry may not be fully protected. RBC quoted sources in the Finance Ministry as saying defense would miss out on 26.9 billion rubles this year, a cut of only around 1 percent but a reversal of a trend of big annual increases under Putin.
A Finance Ministry spokeswoman said work on revising the budget was not yet complete and it did not comment on interim plans.
For non-military state employees, or "budgetniki", cost cutting is already being felt.
Regional heads and management at the Federal Customs Service received a letter on Jan. 22 saying there would be a 10 percent cut in staff "in order to maintain the payment of wages to workers ... at the level of 2014".
According to a copy of the letter obtained by Reuters, managers had to detail their activities, the number of vacancies and come up with plans for their "reorganization" by Jan. 29.
The Federal Customs Service did not respond to a request for comment.
It is a risky strategy. By targeting state workers, Putin may be hurting some of the people who have helped keep him in power since 2000. So far, their obedience has held.
"Since we are in military service, we take orders," said the Emergencies Ministry worker. "And so we cannot say anything against [our bosses]. But how can you run an organization without operators?"