I was just at the Stadthaus this afternoon to de-register before my impending move. I only got there at a little after 16, and noticed that it closed at 16:30. As there were people in line at the Abmeldung counter, I thought I could go to the Steueramt (tax office) directly first. I did, and they gave me a paper to give to the other counter. The lovely gentleman at the Abmeldung counter said that I was very clever to go to the Steueramt first, and had never had anybody else do that before.