Shortest geometric distance from surface in 3d dataset?
Do you just need the distance, or do you need the closest point?

For the closest point, the FLANN library can help, and it has Matlab bindings.

If you only need the distance, you can also use a distance transform. Try googling for "distance transform 3d matlab" for implementations.

Which one is faster depends on the number of "seeds" and "skin voxels".