Must I go back to my gmina and get a 'stale' zameldowania, or is this not necessary?
Yes and no.
In theory it is necessary but in practice it isn't. I lost my Karta Pobytu recently and couldn't find my maldunek either. To get some official piece of paper with my name and address on it, I went to the gmina and asked for a maldunek. They asked to see the notarial deed proving I own my flat and so can give myself permission to live there. I showed them the letter they had sent me demanding local property taxes. They said they needed to see the notarial deed from when I bought the flat. I asked how long I'd go to prison for if I didn't have a maldunek. They said I wouldn't. I asked how much they'd fine me if I didn't have a maldunek. They said they wouldn't. I asked if I really needed a maldunek. They said that officially I do but as long as I don't want to register a car or a company or do stuff like that, I can get by without one.