Okay, I've created an Neutral Evil Cleric. I worship Auril, the Frostmaiden, who abhors fire. What should I do if I've taken the War domain, and I have Flamestrike? Would it lose the fire damage,and just be pure Divine Damage? Or would I be unable to cast it at all?
By RAW, you can cast Flame Strike all you want.
This kind of restriction is technically a roleplaying thing. By the rules, there is nothing to prevent you from casting Flame Strike as a cleric of Auril. The only restrictions on what spells a cleric can cast based on his chosen deity are alignment-based, not based on energy types. However, you're likely going to want to ask your DM some specifics. It's likely that your DM will have a problem with it if your ice cleric casts a lot of fire spells.
Here's how I would run it, if I were your DM. I would give you two choices.
Option 1 would be to leave the spell as is, and have it upset your god when you cast it. This way, you have access to a reasonably powerful fire spell, but you won't want to cast it very much, lest your god get really upset.
Option 2 would be to convert the spell entirely into Cold Strike rather than Flame Strike. It would work exactly like Flame Strike, just dealing cold damage instead. You can create this effect anyway with the metamagic feat Elemental Substitution (Complete Arcane, p79), so it's likely not unbalanced. This option also fits best with the whole ice theme. You might want to run this by your DM and see what they think of it.
The spell would definitely not be converted entirely to divine damage. Divine damage is pretty powerful, and being able to do 1d6/level of damage without any kind of resistance being applied is quite a bit better than having half of that be subject to an elemental resistance.