@Daemetius As you have mentioned that the scope of the CA Policies is set to "All Users", the policies will apply to all users regardless of whether the user is member or guest. Without modifying the scope of the policy it won't be possible to exclude guest users.
One option to exclude guest users is by excluding "All guests and external users" as you have already mentioned and I would suggest you to use this option.
Another option is, you can create a Dynamic Group with a query "userType equals guest" so that all guest users automatically get added to this group and exclude this group from CA Policy.
Although I suggest you to go with the first option but the reason for providing the second option is, let's say in future you would want to exclude all guest users except one guest user e.g. user@Stuff .com. You can then modify the query of your dynamic group to "userType equals to guest" AND userPrinicipalName Not equals user_gmail.com#EXT#@yourtenant.onmicrosoft.com. That way all Guest users will be excluded except user@Stuff .com. Instead of UPN, you may use objectId Not equals <objectId of user@Stuff .com> as well. This would provide you with some flexibility and more control over the User Scope in CA Policy.
-----------------------------------------------------------------------------------------------------------
Please do not forget to "Accept the answer" wherever the information provided helps you to help others in the community.