It depends on trust and understanding between player and GM.
For example, if you were to have a campaign focused around a plague, it would be incredibly shortlived if a first-level cleric or paladin could simply cure it with their spells. Ideally, the GM should have discussed the possibility of plague as a campaign element in advance, and have explained that the regular cures, immunities and resistances will not work against this specific plague.
However...
The wording of your question, "without GM fiat", is the part I'm not sure about. The role of rules is different from group to group. For my group, the rules are a tool that the GM uses to resolve actions, and thus, all rules are GM "fiat". This again comes back to understanding between player and GM - provided the GM is fair and consistent, there should be no issue with afflicting the paladin with a disease, as the player should understand that it is being used as an important part of the game. In saying this, the GM should always have a good reason, and should never be arbitrarily taking away specific features that help to define a class.