none of these users have static IP addresses
Ok, then you can not use host based authentication .

Possible solution:

Use `AllowUsers` in the `/etc/ssh/sshd_config`

for example

 AllowUsers foo@, bar@

or even better

 AllowUsers [email protected].*, [email protected].*, baz@111.*