We may be looking at a failure in the thermostat; see if you can tell when they are open or closed.
Another possibility is the 'dip tube' may have coroded away. You'll find it on the cold water side where it is supposed to take the incomming water straight to the bottom of the heater, keeping the hot water on top for instant use. Turn the water off, take the cold line off, stick your finger down in the hole, bend the finger to wedge it in and pull up. The Dip tube should come out with your finger, Or you may feel the end of the tube where it is broken off. Of course, there is always the possibility that an inexperienced installer noticed it, thought it was part of the packing and threw it away.
Please let us know how it turns out for you.