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, most of them use an air-to-water heat pump to heat the water using heat from their surroundings (this is called a unitary configuration), 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.
If a unitary HPWH is unsuitable, even with outside air ducted in for supply and return, one other option that can be explored in this space is what is called a split system heat-pump water heater. Instead of having a small heat pump atop the tank that draws heat from ambient air in the space the unit is installed in, these units use a mini-split-ish outdoor unit that heats water in much the same fashion as a tankless heater, then pumps it into a tank for storage, with cold water being drawn off the bottom of the tank for reheating. While expensive to buy and install, they provide excellent first hour recovery performance for their tank sizes, while both being highly efficient and capable of operation in a wide variety of climates.
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.