Can the gods strip a paladin of his class?
The short answer is yes. The long answer is yes; followed by a wordy explanation. You seem like an intelligent enough person to have figured this out. The exact body of that lengthy explanation is up to the DM, whether you or someone else.
The rules are direct enough, and at the same time vague enough, to allow for this possibility, if the DM wants to do this. Your argument has set all these people to flipping through their PHBs when (presuming you have read the 3.0 PHB, if not the 3.5 version) you know the explicit wording does not directly say what gods can and cannot do. That is not the purpose of the PHB, that is what the Deities & Demigods book is for; to give DMs ideas on the capabilities of the gods in their games.
And this reason is based on the premise that we're talking about stripping powers as a result of some transgression, sin or evil act on the part of the paladin. If you mean in the broadest sense, then the answer is still yes. Gods are the tools of the DM, devices that allow the DM to interact within the world (campaign) he/she created and do so in a plausible manner. Since the campaign is shaped by the will of the DM, then the gods--under the direction of the DM--can take away a paladin's powers, or do anything else they darn well care to. But that is getting a bit fececious. On that note however, paladin's would be vulnerable to having their powers stripped because they do come from a divine source (whatever that may be) and if that divine source is a deity, or
a deity could somehow block that divine source, then those powers are gone. Sorcerer's spells, Fighter's feats, these are all talents that are developed through those classes, they do not come from a divine source like the powers and spells of a paladin. They can be taken away through direct means by a god--such as Energy Drain, etc.--but they were not granted by a god, or divine source, to begin with.
My question: "Is this supported by the rules as written?"
See above.
I suspect not, because of the following:
1) The core rules allow a character to be a paladin without worshipping or serving any god at all. This argues that paladinhood is something that lawful good characters can generate for themselves. Becoming a paladin is accepting a metaphorical call, accepting a destiny.
2) LG gods can give cleric spells to LN and NG characters, but can't make them paladins. LN gods can give cleric spells to LN, N, and NE characters, NG gods to NG, N, and CG characters--but can't give them paladin powers. This argues that paladinhood is not subject to the whim of the gods.
3) The paladin class description makes no mention of paladinhood being bestowed by the gods or of gods taking it away. There is no more support for them doing this than for them taking away a sorceror's sorcerorhood.
4) The section on ex-Clerics says that clerics lose their spells if they grossly violate the code of conduct expected by their god. But the corresponding section on ex-paladins mentions grossly violating 'the code of conduct'--no mention is made of it being determined or judged by a god.
#1: Your statement does not argue anything. It allows for something. It allows that it is possible for a LG character to become a paladin regardless of religious belief. It allows that becoming a paladin
can be a metaphorical call. It allows that they
can be accepting a destiny. This statement does not support (or deny) your claim (that the gods cannot strip a paladin of his class), because your statements are not the exclusive means of becoming, and remaining, a paladin.
#2: You state two different outcomes; making one a paladin and giving one paladin powers. Those are two different things. Paladins in the PHB are LG, if a character is not LG, they cannot be a PHB paladin (though variants in UA and other sources are possible). But you are trying to limit what gods can and cannot do and there is no basis for that in the PHB. Many gods do have the power to change a character's alignment to LG and then give them levels in Paladin. Many gods do have the power to grant the powers of a paladin to someone who is not LG. If you want specifics, go read the Deities & Demigods since that deals with gods. But your argument here is not supported by your premises.
#3: This statement is incorrect. The support comes in a variety of ways in the paladin class description. You are just wanting it spelled out for you, which, having read the PHB you know it does not. See my answer to your initial question above. It's vague enough in the class description to allow it, while not being explicit enough to exclude other possibilities for the source of their power and/or the removal of such. Your comparison to sorcerer's is misleading as they do not suffer the limitations (following a code of conduct upon which continual use/possession of their powers demands) that paladins do and their powers do not come from the same source. The simple fact that paladin's powers do come from a divine source allows for the possibility that the divine source could be a deity and if it does, then the powers
are bestowed by a deity, and if that deity doesn't want to continue giving those powers (such as if the paladin violated that deity's code of conduct), then the resultant loss of powers is already spelled out.
#4: No mention is made, true enough. But, again, you are questing for specifics where you know there are none. Just because it is not specifically mentioned does not mean your argument is supported by it. At the same time, no mention is made of it
not supporting the idea of gods being the ones to judge and remove powers. This premise works equally well against you as for you, thus providing no extra validity to your argument.
In your haste to support your claims against and denounce others claims in favor of stripping paladins powers, you are ignoring the simple fact that many DMs are likely inserting the code of conduct for a deity that the paladin follows as the paladin's code of conduct, by unspoken (or minimally spoken) agreement with the player. They are also following along with that reasoning such that a) the paladin worships deity X; b) the paladin follows deity X's code of conduct in addition to what is listed in the class description and because of a) and b), then c) the paladin's powers come from deity X and because of c), then d) if the paladin violates b) then the paladin loses c) (his powers). This is not so much a house rule as you seem to assume, but campaign rules from the paladin class description fleshed out agreed upon by the player (of the paladin) and the DM. Thus, the people who posit this (more or less) are not "talking through their hats" but are sharing with you how paladins operate in their game and providing you with the answer to your initial question--as it relates to them and their games; which is what you wanted otherwise you wouldn't have made this topic.
So, the answer to your primary question is yes. And no.
What I am saying is that I cannot find the rule in the D&D core books that says or logically implies that:
1) Paladin's class abilities are given by their gods at will and retained during the god's pleasure.
2) That it is up to the judgement of a paladin's god (an NPC with the game world) whether the paladin has broken any of his or her class restrictions.
3) That a paladin's god can let him or her continue to exercise class abilities after ceasing to qualify for the class, as an act of forgiveness or mercy.
4) That a paladin's god can substitute an alternative (eg. reduced) penalty instead of stripping the powers from a paladin who no longer qualifies for the class.
5) That a paladin's god can require that the paladin go on a quest or perform some other penance as a condition of recovering class abilities.
#1-3: Already explained this above.
#4: See above. If a god grants a paladin his powers, then he can logically reduce them instead of stripping them all entirely. Personally, I think a paladin that makes a mistake should be happy to lose one ability for a day or two as a warning rather than all of them until he atones. While this is not specifically mentioned, it follows with the assumed (or explicitly stated agreement) about paladinhood between player/dm, that if a deity grants it, it can be reduced or otherwise limited as easily as taken away entirely.
#5: This is mentioned specifically in the description for the Atonement spell. Whether it is the paladin's god granting atonement or not seems irrelevant to the description of the spell, but it does mention questing and penance being involved in the atonement to prove the sincerity of the person seeking atonement.
You keep requesting specifics that you know are not there and are not meant to be there. The wording allows for it, and if you're going to DM a campaign that should be enough for you. If you can't comprehend that, you probably shouldn't be DM'ing anything anyway. The game is designed to give DMs (and players) the freedom to hammer out details in a manner that they like, instead of restricting what can and cannot be done. If you do understand that, then you're only arguing just to argue.