Do I have a bad heating element in my electric boiler?
Unlikely an &quot;under-performing element&quot;, they usually either work or don't work.
2 things come to mind:  1)  The flow rate thru the electric boiler is just too great to get the water up to temp, or 2)  You have a control problem.   Did you check to see that all the elements get power?   Is there any staging involved? Your thought that it might have been a bad relay was a good one and it sounds like it might have addressed at least part of your problem.
How closely were you monitoring the system before the problem?   Maybe what you are observing now is how it was operating before, but just didn't know it.