Ameena:
As far as I'm aware, their alignment should be the same as that of their god, but from what I remember I don't think it has to be
Per the rules, it does. I was going to post that paladin's don't even have to choose a deity, since clerics don't, but per the rules they do. However, "(o)nce invested, a paladin is a paladin forever. How justly, honorably, or compassionately the paladin wields those power from that day forward" is up to them. The book suggests that other members of their faith will punish transgressions, but that's going to be up to the GM, and in any case the paladin retains their class abilities, and even their alignment.
Ameena:
they might have a good reason for it, some internal conflict within their character that the player hadn't yet "voiced" in a post.
What if they didn't? I think this gets back to the original post: under what circumstances would you question a rogue or fighter or wizard? Each of them, particularly the rogue, could have strong ties to a guild or enclave that expects them to act a certain way and even has earthly agents to make sure they do. In a world of magic, anyone's "people" could have rigged safeguards such that if they get out of line they lose their class features.
They don't, of course, or don't usually. So, at what point would you say to the fighter, hey, they way you're acting is a bit weird?
Or, better yet, the barbarian or bard: at what point would you take them aside and say, look, I've noticed that you're being kind of lawful. If you don't get more chaotic, I'm going to make you stop advancing in your class.
Monks are even closer to paladins, in that they have to be lawful, yet I've never heard a story about a monk being threatened with becoming an ex-monk. Or a druid! Has anyone ever heard of an ex-druid? Becoming non-neutral (which can happen in two or four different ways, depending) or ceasing to "revere nature" has the same effect on them as it does on a paladin. Yet I've never seen a druid complain about this.
I think the only difference with a paladin is that their Code gives them all these easy buttons to push. If other classes had things spelled out in the same way, I think GMs would mess with them, too.
Flint_A:
5E has no alignment restriction either. I mean, they all fight evil and/or chaos (some focus on undead, some on outsiders, some I believe on naughty fey) but they don't have to be LG. You can be a CE paladin in 5E, you just still hunt other bad guys. (Punisher?)
I recommend not going down the road of applying alignment to fictional characters. Surely you've seen the 3x3 chart of how Batman exhibits every alignment.
Ultimately, alignment is simply not mechanical enough, and too poorly explained for the situations in the original post to be anything other than aggravating. Everyone has their own ad hoc mechanics for it, like the GM mentioned in the original post who has "neutrality points." They want alignment to work like hit points, but it doesn't. It's almost entirely judgment based, and so it's easy almost to the point of being accidental for people to game they system or just look like they're gaming the system.
There's this sense, I think, that a non-LG paladin is somehow gaining some advantage, that they're getting the best of both worlds in the form of divine power and completely free will. Except, they're not that much more powerful than a rogue or barbarian. They're also not as powerful as a wizard, beyond a certain level, and the wizard has free will too.
Flint_A:
Paladins don't even need to be sticks-in-the-mud. I played a Gnome Paladin of Garl Glittergold, which is perfectly rules legal. I was having lots of fun, because my god was all about fun. To a lesser extent, a paladin of Pelor shouldn't be all serious and gloomy. Pelor's a nice god.
By stick in the mud, I meant having to block ideas by the other party members, on the off chance that they would get the paladin in trouble. Fun's fun, but does the paladin stand by when the rogue goes to loot a crypt of Bahamut? Or when the assassin kills a few people - wait, no, that couldn't happen, because the presence of a paladin restricts everyone
else from playing certain classes. It even prevents them from behaving in a way that would cause the GM to make them evil, because then they can't be in the paladin's party anymore.
Those issues are all workable, but it's not hard to see that others might see the mere presence of a paladin as restrictive, and look for ways to needle them.
I like that some editions and some settings don't worry as much about alignment. If alignment does have to matter, I find it works best when it's purely a matter of mechanics, rather than behavior, with alignment neither driving nor being driven by behavior. Like bloodtype: it determines how certain physical interactions proceed, but it can't change you and you can't change it. You can't be certain classes, you can't wield certain weapons (and you might take extra damage from some weapons), and you can't cross certain spell boundaries, and that's that. The boardgame Talisman had alignment that worked that way.