As a quick update - I think that I've figured out the problem. The mnethostid was different between the two sites, once I changed the imported user's accounts to match the target site's mnethostid they appear to let the old passwords work.
We have a little more testing to do, but I think we've got it figured out.
I also can't confirm this, but it looks like either most users have changed their password at least once since we upgraded to Moodle 2.7, or the upgrade itself reprocesses the passwords because the site salt doesn't appear to have any effect, so we plan to omit it completely.