I've heard that you can contact the seller and specially request that he create a medium nuc for you. I have no experience with that, and I'm not sure if he would be willing to do it though.
As far as switching out medium frames for deep nucs, it would be up to the guy if he wanted to take them. Ask, you never know.
But if you are getting a deep nuc, you can't exactly surround it in medium frames. Put the deep nuc in a deep box, then put a medium box over top of it. When the brood size grows, they will eventually move up into the medium box. Then you can take the deep out from under it, and perhaps sell it back to the guy you got the nuc from. Or just hold on to it.