Just to show the precise problem and solution:
My PHP 7.3 comes from deb.sury.org, and they have a php7.3-intl module
root@blackbox:~# apt-cache policy php7.3-intl
php7.3-intl:
Installed: 7.3.7-1+0~20190710.40+debian8~1.gbp032aec
Candidate: 7.3.7-1+0~20190710.40+debian8~1.gbp032aec
Version table:
*** 7.3.7-1+0~20190710.40+debian8~1.gbp032aec 0
500 https://packages.sury.org/php/ jessie/main amd64 Packages
100 /var/lib/dpkg/status
There’s a second package without a version (7.3) in its name, and you need it too:
root@blackbox:~# apt-cache policy php-intl
php-intl:
Installed: (none)
Candidate: 2:7.3+69+0~20190303094641.15+jessie~1.gbp0f7465
Version table:
2:7.3+69+0~20190303094641.15+jessie~1.gbp0f7465 0
500 https://packages.sury.org/php/ jessie/main amd64 Packages
the gist is: If you install PHP from a not-Debian source then all the modules have to come from this source too.