From what I can tell, the Conditional Access policies are working as expected. This is because they are only applied to successful sign-ins. If a sign-in is successful, then the policies are evaluated to determine if the user should be able to access those resources.
If you want to keep the sign-in attempt from getting that far, your best bet is to determine the type of connection being made to Exchange (SMTP, IMAP, POP, etc) and disable it. Exchange Online does a pre-auth step before sending the sign-in to Azure, so if you disable those methods in Exchange Online, it won't forward the request to Azure. Just make sure you don't disable something you need like SMTP for emailing scans. Or you can go back and enable it for those few accounts that need it while leaving it restricted for all others.