I proposed a solution to this problem a couple of years ago. Service providers could monitor how the OAuth token is used by the application and provide a report to users. If a few users could then audit their logs and rate applications, we would quickly flag malicious apps. Services providers would have to make only a few changes to their current OAuth implementations.
My colleagues and I developed this idea in a paper (see: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5421...). Back then we also had proof of concept running on our server.