Thanks to Clemens' comment on my last post, I have managed to track down the problems that I was having with OAuth for Mendeley on Android; it's all callback related.
It seems that callbacks to any protocol except "http" are prohibited.
A callback request to "http://www.martineve.com" will work.
A null callback request ("out of bound"/"OOB") will work and display PIN.
A callback request to "martineve-mendroid:///" will fail.
The failure message varies between "consumer key not found" and a pretty "Something went wrong" page.
I have also tested with addresses that look like URLs from a regex point of view: "eeee://www.test.com". This also fails, so it must be the prefix.
The reason that this feature is required is that Android allows the hooking of URLs to specific Intents, so the web browser can pass the code directly back to the non-web browser application.
In the meantime, I have a workaround for this that should allow me to get on with writing the application. Thanks to Clemens for his original source and here's to hoping the Mendeley devs can come up with a fix, at which point I will make a post detailing how to do this.