Grazie però il problema è che non so in anticipo quanto sono lunghe le stringhe delle JLabel perchè vengono caricate a runtime..

Non c'è una funziona tipo quella dell'html (se non sbaglio) che calcola la larghezza media di un carattere? In modo che a runtime leggo la lunghezza della stringa e sapendo che quella più lunga è ad esempio da 30 caratteri, moltiplico per la larghezza media e posso impostare minWidth.. pensate che sia possibile una cosa del genere..?