Is it possible to run a water-heater on a undersized breaker for years?
TL;DR 25A is the right size
First of all, your hunch is correct. 4500W/240V = 18.75A. That should be on a 25A breaker because it is a continuous load - if you pulled water out at a rate that the water heater could not keep up with (or barely keep up with) then the elements would stay on &quot;forever&quot;.
You also did the right thing changing the wire. 12 AWG is fine for 20A, but since you really need 25A here, 10 AWG is the right size. It is a good thing you did not have 14 AWG previously (to match a standard 15A circuit) because that would have been undersized considering what was actually happening - an 18.75A load.
So why didn't it trip? Breakers are not some magic device that trips at exactly the stated max. current. In fact, you wouldn't want that because an appliance that needs a little extra power at startup would frequently trip the breaker. So a 15A breaker might not trip on an 18.75A load for an hour. Another 15A breaker might trip on that same load in 1/2 hour due to manufacturing differences. But any 15A breaker will trip very quickly if it gets a 50A load. All of this is factored into the electrical code. For example, a 12 AWG wire is rated for 20A, but in reality it can carry much more for short periods of time, so a 20A circuit with 25A for a little while isn't going to suddenly burn up the 12 AWG wire.
My guess is that your breakers were just barely tolerant of the 18.75A current flow but gradually became more and sensitive and tripped sooner. Then you replaced it with another 15A breaker, which was probably closer to the 15A specification than the original and it (correctly) would trip after a little while but not immediately. Then you replace with a 20A breaker which can handled 18.75A &quot;forever&quot; but which is still undersized (but would be correct for 12 AWG wire) and 10 AWG wire (which is the right size).
So put in the 25A breaker and permanently switch to 10 AWG wire and you're all set.
I would check anything else done by that plumbing company for safe &amp; correct installation. While a plumber is not an electrician, the crew putting in a water heater should know what to do and what size breakers &amp; wire to use. If the 15A breaker and 12 AWG wire were from the previous water heater, the installers should have told you it was not correct and either swapped it at the time or stopped work until you got an electrician to switch to 25A/10 AWG. But they likely didn't because they wanted to get in, get out, get paid. So I'd worry about other &quot;shortcuts&quot;.