> It's not too long ago they would ask for information faxed using company letterhead, as a form of legitimization.

I had PayPal ask me for exactly this (emailed rather than faxed) recently for my PayPal business account!