Yup I get that. I've been getting it for ages, but a couple of recent occasions has been when I was collecting money for charity, and some woman stopped and spoke to us, my friend said something about me using female pronouns and she just stood there gaping, saying, "She?! Did you say she?!"
Often when we're leaving the base we live on the guard says "Have a good evening lads," or something similar, which sparks up a conversation about whether or not I mind always being seen as male. As I'm not out to them I just have to brush it off, but it's hard not being able to show how happy it actually makes me, and tell them that actually, they're wrong and the guard was right.
Even when I'm not with anyone it causes problems for me, for example the other night I was checking into the hotel here (staying for work), and it took me quite a while to convince them I was the person who was staying in the room. It could have been a lot worse as a few moments before the manager I will be under in June was there helping me get my bags in, but it was still awkward enough.
Receptionist: When will Miss [Lastname] be arriving?
Me: That's me.
Receptionist: Miss [Lastname]?
Me: Yes.
Receptionist: Miss?!
Me: Yes.
Receptionist: M-I-S-S?!
Me: YES!
A similar thing happened when I was having my meal last night too, she called me sir when collecting my plates (quite a rare thing here, we don't really sir/ma'am people often in the UK, so it was nice, but I knew what was coming), and as I have an allowance for meals at the hotel instead of paying with cash I just have to give them a chit saying it's paid for, which conveniently only says "Miss [lastname]" on. She was really awkward when she came back, and I saw them all staring at me when she was signing off the chit, and when I walked past to leave. I almost didn't eat tonight because I didn't want the humiliation again.
So, yeah. It's a normal thing I think. I wouldn't worry that it means that you aren't actually a guy, or are pleased to be gendered correctly. It's just embarrassing for you, and for them, to have to "correct" someone. It's embarrassing because society says that it's bad, awkward, and generally not socially acceptable, to misgender people, for example men who aren't "manly" enough get called girls, and women get teased for being "masculine", especially in schools. It's not nice, it shouldn't happen, but unfortunately it does. I find it horrible to have to "correct" people, because I'm lying about a fundamental part of who I am.