I think if your having to build your character in a certain way because you are worried that you will be continually 'screwed over' then you have a problem.
If your DM makes it difficult on specific occaisions for certain characters to be as useful as they would be under usual circumstances but builds in different ways for them 'to be useful' or 'resolve the situation' then there is no problem at all. But a certain class shouldn't be picked on more than others just because they are casters. Nor should the challenge be simply, 'none of your powers work here'.
I'd be interested to know from the OP if the initial fear that the cleric could be 'screwed over' if he doen't invest in some melee ability was from his experience with this specific DM's play style, or was it just a projection of certain difficulties casters faced in other editions he has played.
In any case, if it is a problem with a simple feat called 'melee training' those problems are swiftlly resolved.