У моего хостера стоит mysql 5.0, но password() шифрует по старой схеме (16 байт). Видимо где-то выставлена такая настройка 
Можно ли в скрипте задать принудительно новый метод шифрования - мне нужно использовать базу юзеров с другого хостинга, а пароли там в 41-байтовом хэше 

Спасибо!

Нет. Точнее можно задать старый алгоритм, но не новый.
Применительно к таким случаям есть предостережение не использовать функцию PASSWORD для шифрования паролей пользователей, не относящихся к пользователям MySQL.

Да, OLD_PASSWORD() шифрует по старому, но вот чтобы по-новому...