The POCO person was wrong. Start at 422.10(A). The branch circuit rating cannot be less than the marked rating of the appliance. In your case, the marked rating is 4500 VA at 240 volts, which is equivalent to 18.75 amps. So the breaker has to be at least 18.75 amps, but this article does not give a maximum breaker rating.
Next, go to 422.11(A). If the water heater had been marked with a maximum breaker size, then you would have to meet that requirement. But it is not so marked. So here again the code does not give a maximum breaker rating.
Next, go to 422.13. You didn't give us the water volume of the heater, but I think it is a good bet that we have to consider it a continuous load. That makes the minimum breaker rating 18.75 times 1.25, or 23.4 amps. So a 25 amp breaker will satisfy the code. But here again this is a minimum rating. Nothing prohibits us from using a higher rated breaker, so long at the conductor can handle the current that the breaker will be able to pass along.
Finally, go to 240.4(D)(7). Presuming your answer to hardworkingstiff's question is "yes," then tor a #10 copper, the maximum breaker rating is 30 amps.