I just found this can also happen if you have an org policy blocking the ability to add "allUsers" to an IAM permission. In my case it was the org policy iam.managed.allowedPolicyMembers

Basically the issue here is that it deploys the functions, tries and fails to set permissions on those functions (for whatever reason you happen to hit) but it leaves those functions deployed. Then, the next time you go to deploy, it sees the functions there and deployed and decides to report "success" on subsequent deployments, even if the IAM permissions never get set correctly.

It can drive you crazy because it appears like an intermittent deploy failure, combined with the fact that newly deployed functions are failing and old functions with the exact same config are working inexplicably. It turns out some IAM policy changed at some point in time so things deployed before then worked and after then are silently not working.