R - 148 137 chars
(so, far away from the rest of the competition but still)
f=function(n){s=sapply;which.max(s(lapply(strsplit(s(4:n,function(x){q=n;r="";while(q){r=paste(q%%x,r);q=q%/%x};r})," "),`==`,4),sum))+3} Basically transform the input from base 10 to all bases from 4 to n (using modulo %% and integer division %/%) and pick the index of the first one having the most 4s.
f(624) [1] 5 f(444) [1] 10