Player's Handbook II (3.5) / Divine Conversion / p193
This is a sidebar at the bottom of the referenced page, which is part of a section on rules for retraining. If you don't have the book, here is the direct quote:
DIVINE CONVERSION
As noted in the Player’s Handbook, a cleric who grossly violates the
code of conduct imposed by his deity loses all spells and class
features and cannot attain any more levels as a cleric of that deity.
All these penalties remain in effect until he atones. But what if he
doesn’t want to atone? What if a cleric of Hextor finds new meaning
and purpose in serving Heironeous after a dramatic conversion
experience? Such a character need not become a multiclass ex-cleric of
Hextor/cleric of Heironeous. Instead, Heironeous can simply reinstate
the character’s cleric powers once he has proven his loyalty, talent,
and ability.
A cleric who changes his patron deity must complete a quest to prove
his devotion to his new patron. The nature of the quest depends on the
deity, and it always clearly reflects the deity’s alignment as well as
his or her goals and beliefs. To start the process, the cleric must
voluntarily accept a geas/quest spell cast by a higher-level cleric
of his new deity. During the quest, the cleric has no access to spells
or cleric class features—except his weapon and armor proficiencies,
which he does not forfeit.
Upon completing the quest, the cleric receives the benefit of an
atonement spell from a cleric of the new deity. The character then becomes a cleric of the new deity and is inducted into the clergy
during an appropriate ceremony of the DM’s choosing. After selecting
two of the new deity’s domains in lieu of his old ones, the character
has all the powers and abilities of his previous cleric level, plus
the granted powers of his new domains.
This method is the only one by which a cleric can change his deity.
The retraining rules can’t be used to accomplish this task—it is
simply too substantial a change in the character’s identity (not to
mention his source of power) to chalk up to a bit of practice in his
off hours.
This answer essentially reflects the ruling already found in the Forgotten Realms Campaign Setting, but it may be useful to know it's also located in a setting-independent rulebook, just in case there are any sticklers out there.
In general, it doesn’t need to be a problem
You should trust your players before even starting a game, and as long as you trust your players, you don’t need to know the complicated details of how their classes work, just the general gist of their capabilities and limitations. They are aware that you are new, so they should be trying to help reduce your workload by taking care of their own characters.
If the Challenge Rating system worked better, you wouldn’t even need to know that, but unfortunately CR is almost worthless so you have to think about what your players can actually do versus what a monster can actually do, regardless of their relative CRs.
In this specific case, they have me worried
The Diplomacy rules (and, to a lesser extent, the other social skills) are extremely simple and tend to work pretty poorly. Most groups basically ignore them and determine success in social encounters primarily through roleplay where players and the DM try to roleplay a given character’s relevant social skills accurately.
However, this becomes extremely difficult when Diplomacy is optimized, because by the rules Diplomacy DCs cap fairly low and it’s possible to make Diplomacy hit the highest DCs in the book very reliably, even from a low level. Assuming you don’t want to play a game where the PCs can effectively mind-control everyone they talk to (without magic!), you have to ignore the rules, but that gives you very little idea of how good a, say, DC 40 check should be.
Worse, 3.5’s ruleset focuses heavily on combat. That’s what 90% of the rules exist to define. If you are not fighting, the system is extremely bare-bones; most of it comes down to “roll a d20, add your bonus, hope it’s high enough. If not, try again if you can.” There’s just not much available in the way of tactics or choices, it’s just a matter of how well-prepared you are and how high your numbers are. This does not make for a very interesting game.
Thus, pacifist diplomats simply don’t fit 3.5 very well. The system just isn’t good at describing the adventures of such characters. There are numerous other systems that handle it far better (I strongly recommend FATE here), but ultimately Dungeons & Dragons has been shaped, from its roots to the present day, to focus primarily on, well, exploring dungeons and slaying dragons. It can handle more complex games, but the further you get from the dungeon-diving paradigm, the less well D&D is going to work. Pacifist diplomats is about as far from that as you can get.
Finally, I suspect (and fear) that they may be using the apostle of peace class, and the associated Vow of Peace feat, from Book of Exalted Deeds. In addition to all the above problems of trying to force a very different style into D&D’s fairly narrow focus, the apostle of peace is ludicrously overpowered (high-level spells earlier than you’re supposed to get them, extremely potent defenses, radiates an aura of “you can’t do that,” etc). Worse, if there are other members of the party, having the apostle of peace around will badly impact their characters. With an apostle of peace as an ally, you take penalties for violence (even though you do not have the Vow of Peace feat yourself), plus you are magically inhibited from being violent or aggressive (it’s almost impossible for a barbarian to use Rage with an apostle around, for example, unless the barbarian wants to kill the apostle).
Conclusion
All games revolve around what is known as a “social contract,” the general agreement among the players (DM included) about what sort of game they want to play. Most groups don’t explicitly talk about the contract, it’s purely based on the setting, the system, the people (assuming you have played together before), and the stated premise of the campaign. Part of the social contract at many tables is to keep your character within an acceptable power range, neither overshadowing other players nor being dead weight. Assuming your group is full of mature and friendly players, a DM should not have to know intricate details of each player’s character; each player should be designing the character to fit within the social contract of the game.
However, the system that you are playing is also a part of the social contract. Choosing Dungeons & Dragons implies certain things about the game you are going to play, and choosing 3.5 specifically implies certain other things. Considering the heavy focus on combat in the rules of 3.5, combat is usually expected, both by the system itself and by the people who agree to play it. Thus, most players in a 3.5 game are going to show up having spent a fair amount of time, in the construction of their character, thinking about how that character will act in a fight. For one or two players to show up with a pair of characters that not only do not intend to fight, but indeed even expect to prevent others from fighting, is not obeying the usual social contract expected of a 3.5 game. It both means that the system is not well-tailored to the game, and that other players who were operating under more typical assumptions may have wasted their time developing characters whose skills will go unused. Plus, as you have noted, it wastes a great deal of your time, having prepared for a more typical 3.5 game.
Thus, I would consider your players’ characters to be outside the scope of the social contract for this game. They just are not appropriate. You should ask them to shelve those characters for another game, quite possibly in another system that better handles them, and create more fitting 3.5 characters.
Best Answer
Guidance of the avatar is the best skill-pumping spell in the game, without question: it gives a +20 competence bonus on a skill check. (2nd-level spell)
Divine insight in Spell Compendium gives an insight bonus of up to 15 (at CL 10th), so that’s another +15. (2nd-level spell)
Surge of fortune from Complete Champion grants a +2 luck bonus. It can also be discharged to treat one roll as a natural-20. You can cast two of them on yourself, one to discharge and the other to stick around so you get the +2. (5th-level spell)
Ray of hope from Book of Exalted Deeds grants a +2 morale bonus to skill checks. (1st-level spell)
Share talents from Player’s Handbook II can grant a +2 untyped bonus as long as either you or an ally has at least one rank in Diplomacy. The other target need not assist in any way during the speech. (2nd-level spell)
If you can cast Evil spells, and have an Evil ally who doesn’t mind a little pain for this, you can cast willing sacrifice over an over until you get the maximum +5 untyped bonus. (3rd-level spell)
Interfaith blessing could give you +1 untyped to skill checks, if you worship Boccob, Corellon Larethian, Vecna, or Wee Jas. A worshiper of Garl Glittergold, Olidammara, or no deity has a 25% chance of getting this bonus as well.
All told, this hits DC 61 before ranks or Charisma are even considered, and without relying on willing sacrifice or interfaith blessing. RAW, that’s sufficient to turn even a Hostile crowd Friendly, and a crowd that is already Friendly or Helpful will become Fanatic. Doing better than that means hitting DC 90; maxed ranks at your level will get you halfway there. Of course, no one should ever play Diplomacy RAW.
There are no spells that directly interact with Diplomacy in a useful way; most give penalties, and others give smaller typed bonuses than the bonuses above.
Intimidate does have divine presence which grants a +5 sacred or profane (depending on your deity) bonus, and that bonus increases to +10 and then +15 for each alignment axis on which the audience opposes yours (e.g. +15 if you were LG and the crowd was CE). But Intimidate is usually not a great choice.
Eagle’s splendor is still your best choice for improving Charisma. Lesser visage of the deity and visage of the deity have the same +4 enhancement bonus, along with other bonuses that aren’t useful to you, but that’s it.