As most you say, this is a known issue. I never had this warning when I was using Snow Leopard. Began with my new MacBook and Lion.
And for what matters, in my case, it happens to apps and unzipped files (images or pdfs)... Every app I downloaded from the Mac App Store works fine. Skype, Chrome, Firefox, downloaded from their sites with Safari, also shows the warning every time I open them, even in the same session. I don't mind having this one time, the first time I open an app or downloaded file (always from sites & people I trust) but every single time since downloading or installing is annoying.
The terminal command to completely disable the warning is dangerous of course, if it feel dangerous to someone, then just don't use it.
I do prefer the termnal command that turns off quarantine of folder mentioned above, or removing the quarantine just for the app:
xattr -d -r com.apple.quarantine /Path/to/application/
Hope this helps.