Ok, I can confirm Foreman REX works when a VM is recreated IF the host is deleted and recreated in Foreman afterwards (before running a REX job).
Probably because, as you mentioned in your comment, Foreman then considers that this is a new REX job for that (new) host and then cleans up the entry in the foreman-proxy’s known_hostsfile (but no purge triggered by the host delete action as on Foreman 3.13) prior to opening the ssh connection.
Thank you for the help!