I found a way to shave my running time down from 5.75 seconds to about 0.1 seconds. Basically, I just eliminated a lot of unnecessary multiplications and palindrome checks.

NotPalindrome[x_] := (y = ToString[x]; y != StringReverse[y]); BiggestPalindrome[n_] := (x = 1; For[i = 10^n - 1, i > 10^(n - 1) - 1, --i, For[j = i; m = i*j, j > 10^(n - 1) - 1 && NotPalindrome[m] && m >= x, --j, m = i*j]; If[m >= x, x = m]]; x)

It takes about 0.21 seconds to compute the largest palindrome that is the product of two four digit numbers, and about 19.5 seconds to compute the largest palindrome that is the product of two five digit numbers.