So, this time I decided to get there *before* the doors open... and I was glad I did so.
The office opened at eight, and when I arrived twenty minutes earlier, there was a long queue of people standing in front of the door. They opened the doors at ten to eight, and people slowly filed in and pulled numbers from the machine. I got number 33, which was better than Tuesday's 45... but today they were only open to the public for four hours, so they didn't have as many numbers anyway. (They were exhausted just before eight o'clock -- so anyone who arrived *after* the official opening hour had to come back on Monday.)
After about 2:45 hours' wait, it was finally my turn. This time my paperwork was sufficient and I now have a permanent residence permit for Germany. Yay me! Now I don't have to go wait around there for hours on end every five years. *Phew*