Apple - How to get rid of "application downloaded from the internet" message when installing homebrew casks?

Wohoo! I just realized that there is apparently now a built-in solution to the problem! Homebrew offers a --no-quarantine flag. That means one can now install casks without the annoying message, by using

brew install --no-quarantine calibre

or

brew reinstall --no-quarantine calibre

Update: There is currently a bug in Homebrew that prevents the latter command (reinstall) from working.

As you mentioned in your update, you can open the application as an admin user. A more direct way is to run this command as an admin:

xattr -r -d com.apple.quarantine /Applications/Calibre.app

More of a workaround than a solution: Launching the App from an account with admin privileges once, makes the message disappear also for the non-admin account. Not sure if this is a bug or a feature... In the past it used to work like that also from non-admin accounts.