I can finally report that I got it right. While working on a different problem, I saw how easy it was to scan through a sorted array. I did a bunch of stupid things with that code, using the BigInteger-class itself was a weird decision, as a double can handle those numbers. Anyway, I started from scratch after realizing that and wrote this in two minutes:

import java.math.*;
import java.util.Arrays;
public class EulerProblem29 {
public static void main(String[] args) {
double[] tall = new double[10000];
int teller = 0;
for (double a = 2;a<=100;a++){
for (int b = 2;b<=100;b++){
tall[teller] = Math.pow(a,b);
teller++;
}
}
Arrays.sort(tall);
for (int c = 0;c<tall.length;c++){
for (int d = c + 1;d<tall.length;d++){
if (tall[c] == tall[d]){
tall[d] = 0;
}
}
}
int teller1 = 0;
for (int e = 0;e<tall.length;e++){
if (tall[e] != 0){
teller1++;
}
}
System.out.println(teller1);
}
}