I faced the same problem and figured it out.
Shortly speaking, the class must be compiled before exec:java goal. (It surely works without test-compile phase if the class is already compiled by other user action. Note that Pascal Thivent, in his answer, invoked mvn test before exec:java.)
$ mvn -Dexec.mainClass=... -Dexec.classpathScope=test test-compile exec:java
You can prove it for yourself if you want to see the ClassNotFoundException again.
$ mvn -Dexec.mainClass=... -Dexec.classpathScope=test clean exec:java