There are actually 3rd party services that mail companies can use to check how trusted an IP is. So a lot of times, they'll provision an EIP on AWS, run a check against that service, use it if it's clean, and release and try again if it's not.
It does lock you to using EIPs though, which makes it a bit harder to scale up.
You might be interested in a provider-agnostic email API I am building to to avoid EIP/provider lock-in and have the security of multiple dedicated IP providers. Check it out: flutemail.com
