But once you did that it wouldn't be stateless anymore as you'd need to connect to their server every time to check on the state of that site's password. This makes it not that much different from traditional online managers where you have to connect to the site to retrieve the password.

There is still the benefit that the passwords can't be exposed by a compromise of the service. Presumably it doesn't store your master password anywhere, so all they'd get is the site and counter info.