Turns out I have not looked good enough at my stack trace, the problem is not that the external JAR is not included.
The problem is that Android platform is missing javax.naming.* and many other packages that the external JAR has dependencies too.
Adding external JAR files, and setting Order and Export in Eclipse works as expected with Android projects.