0K>В общем, удалось расковырять их алгоритм.

а я добрался ответить только сейчас.
если столкнёшься ещё с тем же — можно попробовать поиграть с байтами опираясь на два факта:
1) если бы существовал MyInterface с нужным методом в именованном пакете, а нужный тебе класс implements MyInterface,
то закастить к интерфейсу или Class.forName(нужный класс).asSubclass(MyInterface.class).newInstance(); без проблем.
2) до javac 1.4, это("достучаться" до unnamed package) было можно, т.е. нужно просто найти jdk 1.3 и скомпилить класс-wrapper этим jdk

к примеру, вот такой алгоритм скорее всего прокатит, если таки нет jdk1.3 :
0) добавить MyInterface c нужным методом в именованный package
1) добавить asm-ом, ну или jassist-ом "implement MyInterface" в нужный класс (в unnamed package-е).
2) вытаскивать в именованном пакете класс Class.forName(нужный класс).asSubclass(MyInterface.class).newInstance();
или кастовать к интерфейсу, если приходит ссылка на Object.

дисклеймер: вероятно, сложность однократной расшифровки алгоритма иногда проще )