Sorry, I somehow made a typo in the quoted text, the RFC says

  Verifiers MUST be able to validate signatures with keys ranging from 1024 bits to 4096* bits

So mail providers MUST support up to 4096 bits if they follow the latest RFC.