What you heard at the plumbing supply house is correct -- single conventional electric water heaters are no longer being made in sizes larger than 55 gallons for energy-efficiency reasons. However, you do have options here.
Shrink the tank, boost the first hour recovery
One option would be to look for a tank in the 50-55 gallon class that has very high first hour recovery capability (equal to or better than the first hour recovery of your current heater). This would probably pull more peak power than your existing State, but could easily match or beat it for total energy consumption by way of being better insulated than the old heater. However, finding high first hour recovery electric water heaters may be difficult unless you look at commercial units, and your circuit may not be large enough for this.
Go with a heat pump water heater
Over-55-gallon electric tanks are being replaced with clever little devices called heat pump water heaters. As their name implies, they use an air-to-water heat pump to heat the water using heat from their surroundings, instead of an electric heating element. This is your best option provided you have a waste heat source in the room; otherwise, the heat pump water heater may drive your heat bill up/struggle to produce hot water during the heating season. Some heat pump water heaters are known as "hybrid" heaters and have electric elements that supplement the heat pump in high demand situations.
Use two smaller heaters
You can connect two smaller tank-type heaters in series or parallel (either works, although both configurations have advantages and disadvantages) to meet your hot water needs. This allows you to use standard tanks to fit the bill, but requires two circuits. You can also use a tankless heater as a booster feeding a tank-type heater, but electric tankless heaters have extremely high instantaneous power needs, so it's generally better to use two tank-type heaters instead unless you are dealing with extreme hot water loads that exceed the first hour recovery capability of any other configuration.
A fully tankless setup can be used as well; however, electric tankless heaters are monsters when it comes to peak power consumption, pulling over 100A compared to the 30A draw of a standard-issue residental tank. As a result, electric tankless heaters are probably not the best choice unless you have a large electric service (upwards of 200A) and are not going to get dinged by your utility with peak charges, either.