Great discussion.
However hackneyed it may be, I'm working on a campaign world where the "Gods" have been locked out of the multiverse by a long forgotten cataclysm. They are no longer able to act on the material plane or effect the multiverse in any way. They have been (all but) forgotten and are no longer worshipped. However, the divine power of the absent "Gods" is still present in the multiverse and can be accessed through belief in the Ideals represented by the forgotten gods.
Thus I'll be permitting deity-less clerics in my world. In fact all Clerics will be godless. The Clerics in my world strive to be the very embodiment of the Ideals (domains) they represent, but they do not "worship" anything.
Obviously, logic must rule when giving my concent to a players choice of domains for their character - can't have a Cleric with Good, and Evil domains, or a Good-aligned character selecting a domain unabiguously associated with Evil - like Hatred or something. I might be convinced to permit something like Fire and Water, but it would take a very good character concept.
That said, I am interested in war-stories from DM's who've tried deity-less Clerics. Are min-maxed domains a real potential problem or just much ado about nothing?