A classical article on the subject, quite old now, has concluded that approximately 80% of diagnoses can be made from the history (ie a structured interview) with a further maybe 10% from physical examination and maybe 5% from additional investigations (http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1673456/). Obviously, the requirements for modern medicine and the available means are a bit different. Nevertheless, any serious doctor will tell you that the history taking and the physical examination are the most important parts of an encounter with a patient.
This is a direct result of Bayes theorem: the interview and physical define the "prior" probability for any diagnosis and any further investigations will only serve to modify it by a certain degree (confirm or exclude). With the exception of some quite aggressive diagnostic methods, like a biopsy or laparoscopy, which will never be recommended upfront, most investigations are generally not sufficiently sensitive or specific enough to give a conclusive diagnosis.
Finally, the physical (which cannot be done via Skype) is also a very important component of the physician and patient relationship. An encounter without physical examination seems, in my humble opinion, quite superficial. Patients are generally more satisfied if you take the time to carefully examine them.
That being said, Skype can be a decent solution for people living in remote areas where transportation can be a real problem. Skype for people living in major cities is a bit silly, I think.
PS. I am physician, but I am curious to hear what you think about the value of physical examination.