> They will happily redirect the request
Doesn't HSTS thwart this? Unless paypal.com were omitted from the preload list, AND you had never browsed to paypal.com before with that browser, it should refuse to connect over HTTP and the attacker won't be able to issue their redirect. It will try HTTPS instead and immediately fail out of certificate validation.