As far as I know, your points 1) and 2) are the main issues. Having to work myself with software talking to Windows hardware drivers from MacOS via Parallels, I can understand the problems of this additional complexity.
The lack of staff is especially a problem as the employees have to be trained in a lot of different areas of law and procedures (because the Bürgerbüros/KVR are quite generic and offer all different kinds of services), so you can't just shift employees around... and Munich has the added problem of extremely high living costs combined with extremely low, un-competitive pay.
Thank you for confirming my suspicions, fellow Munich-dweller.
While the mayor's office even publicly admit that the staffing situation is atrocious, they probably can't resist to pass at least some of the blame.
But they also deliberately shrunk the staff levels a few years ago to save money.
4) and 5) would've been problematic on Windows, too (in fact, Windows would've struggled even more with 4).
Hopefully 2, 3, and the remainder of 1 will continue to improve, but they are indeed obstacles even today (users tend to get frustrated with Linux's "quirks", and the driver situation is still abysmal for printers and scanners, which are vital in offices; Wine is getting good enough to be a viable solution in some situations, but it's by no means a universal solution at this point).
I worked there. The biggest problems back a few years ago:
1) So-called "Fachverfahren", basically software for stuff like managing drivers' licenses or other bureaucratic procedures, is written and supplied for Windows only. Often enough that meant Munich had to pay a boatload of money for a Linux port. Or the software HAD a Linux port, but for RHEL or other "enterprise linux" crap distros - which meant using stuff like "alien" or, worse, manual repackaging to make them compatible with Ubuntu. Yay for version hell - statically linked programs were an exception.
2) DRIVERS. There's a lot of custom hardware - special printers for printing on documents like ID cards, fingerprint readers for the new national ID cards, RFID readers with support for said ID cards... you won't believe how much stuff there is. And all of this needs to have Linux drivers and tooling.
3) Employee training. Back in my days KDE was used (and I believe it still is), but it's different enough from Windows that people need training. And there's 35k of employees, most of which don't have any IT experience outside from their Windows computer at home.
4) The computers themselves. Let's just say that the computers in any public agency are almost always horribly outdated. Many users complain(ed) about the speed of LiMux, which mostly was caused by old or underpowered (esp. RAM, given that OpenOffice and Firefox are really really memory hungry) systems.
5) Networking. Depends on the building and agency, of course, but e.g. my school was connected via a 16 mbit uplink, over which the entire Internet traffic went...
I believe the biggest problem LiMux had and still has is a lack of proper funding - especially for hardware.