TL;DR: Use xattr -rc /location/MyApplication.app (see here).

I use to save all my apps on my NAS. The other day I wanted to use an old app for colour palette. I've downloaded it from my NAS and...:

“MyApplication” is damaged and can’t be opened. Delete “MyApplication” and download it again from the App Store!

What? It's my app! So, apparently, Yosemite checks new apps (the same old "Your app was downloaded from http://www.example.com" message) but the apps are also verified against the store. It may or may not have something to do with certifications, but running:

#--
xattr -rc /location/MyApplication.app
#--

solved the problem (see the xattr manual for more details). Above, MyApplication.app is the "damaged" application.

Note: You may have to run the command against the mounted image in /Volumes

HTH,