The CART algorithm processes NA quite easily ( rpart package ). Then you can always access packed trees with help rpart, possibly through the ipred package .
I heard that multidimensional adaptive regression splines ( marsin the mda package ) handle missing data well, although I don't have much experience with it.
In addition, k models of nearest neighbors (and, in general, the kernel) can be modified to deal with missing values quite simply, but implementations cannot do this out of the box. But, apparently, it would be as simple as adjusting the distance metric to consider only pairwise complete cases. I am less familiar with specific R packages that do more than vanilla knn models.