Вы можете использовать только время в миллис, если вам не нужен сильный UID. Или вы можете получить реализацию UUID из J2SE и перенести ее в J2ME. Таким образом, UUID должен храниться в RMS.
Одним из лучших способов является создание серверной части и распространение приложения только через этот сервис. Когда новый пользователь пытается загрузить приложение, вы можете поместить в манифест и указать любой UUID, который вы хотите, и использовать его в своем приложении через MIDlet.getAppProperty (String uuidPropertyName);