I think this has been asked before (especially on the finances forum or in general residency) and the consensus seems to be that interview expenses for medical school or residency CANNOT be deducted. I do not know about fellowships though...
I don't know why this is, but I believe there is some technical explanation that involves residency being considered "education."