java CLASSPATH not working on command-line

You seem to be missing some fundamental concepts here.

The classpath gives a list of directories and JAR files to search for needed classes. When trying to load a class foo.bar.MyClass that is not part of the standard library, the default classloader will look for it in each classpath element in turn, in order, until it finds the class or runs out of elements.

Note well, however, that it searches by fully-qualified name. For classpath entries that are directories, that means that it looks for foo/bar/MyClass.class relative to the directory. For classpath entries that are JAR files, it looks for foo/bar/MyClass.class relative to the root of the JAR. Classes that belong to the unnamed default package are a little special, or so it may seem, because their class files (e.g. InDefaultPackage.class) are expected to be located directly in the root of the designated JAR or directly in the specified directory.

Compiling without -classpath does not work (I thought -classpath defaulted to .?)

$ javac Example.java 
Example.java:2: error: package javax.mail does not exist

The classpath does default to .. This is the name of a directory, so when searching it for classes in, say, the javax.mail package, it looks for a subdirectory javax/mail, and if that is found, it examines the class files within. Note that it does not descend into JAR files it discovers in the directory tree. It looks only in those JARs explicitly named in the classpath.

The error message is telling you that javac didn't find any classes at all from the javax.mail package. You could have solved it either by specifying the JAR in the compilation classpath (as ultimately you did) or by unpacking the JAR in the current directory.

Specifying the -classpath helps, the program now compiles and produces Example.class:

$ javac -classpath javax.mail.jar Example.java
$

Note that the compiler will store the classfile in a directory structure corresponding to its package, just where the java command will look for it.

Running the program produces this error:

$ java -Xdiag -classpath javax.mail.jar Example 
Error: Could not find or load main class Example
java.lang.ClassNotFoundException: Example
    at java.net.URLClassLoader.findClass(URLClassLoader.java:381)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:424)
    at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:335)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:357)
    at sun.launcher.LauncherHelper.checkAndLoadMain(LauncherHelper.java:495)

You clarified in your answer that you solved this problem by removing a package statement from Example.java. That's ok, but it doesn't really explain the problem, which is that java expects you to give it the fully-qualified name of the class. That includes the package name if the class is in a named package. Thus, if Example.java contained this package statement:

package com.my;

then the class name you would need to specify to java would be com.my.Example. You specified just Example, which designates a class named "Example" in the default package, and your solution to the class not found problem was to move your class into the default package.

Note also that it is conventional and helpful to lay out your Java source files, too, in a directory structure matching their package structure. Thus, the source file for class com.my.Example would conventionally be located in com/my/Example.java. The Java compiler will rely on this scheme to locate sources for classes that it does not find.

Running java without -classpath causes the JNI to not find javax/mail even though it's in the directory.

$ java -Xdiag Example 
Error: A JNI error has occurred, please check your installation and try again
Exception in thread "main" java.lang.NoClassDefFoundError: javax/mail/Address
    at java.lang.Class.getDeclaredMethods0(Native Method)

No, javax/mail/Address was not in the directory. It was in a JAR file in the directory. That's not at all the same thing, and the difference is significant.