Why does finder report my applications are in the trash when I use Open With?
As Lri suggested in a comment, rebuilding my Launch Services seems to have fixed the issue.

To rebuild launch services run the following from a Terminal:

 /System/Library/Frameworks/CoreServices.framework/Versions/A/Frameworks/LaunchServices.framework/Versions/A/Support/lsregister -kill -r -domain local -domain system -domain user


Took just a second and cleaned up the duplicates too.