I had a look to the way this problem is solved for Ubuntu in
Launchpad (make libsane-hpaio depend on hplip) and I believe this
solution will prevent users from installing libsane-hpaio in
stand-alone (without hplip), as publicized in the package description:
"This package is useful for a minimal footprint headless scanning
solution"
I may have seen only a limited part of the problem, but from my own
experience, it seems that the only thing missing is
a /etc/hp/hplip.conf containing a stanza with the path to the
data directory. Like this:
[dirs]
home=/usr/share/hplip
And of course, a little explanation in a README.Debian.
Making libsane-hpaio recommend hplip will prevent problems for most
users, and will allow minimal installation (I can use my psc1510 with
only hpijs and libsane-hpaio), even if creating the /etc/hp/hplip.conf
like above solves only a part of the problem encountered by the
original poster.