>Tenho um WebService (feito em VFP) que é consumido por inúmeros clientes de formas distintas (Cliente VFP, Páginas ASP, programas em VB, Office etc). Como eu poderia incluir criptografia nestes dados? Existem alguma forma sem ser preciso alterar o lado cliente que consome este WebService?

sem mexer nos clientes eu imagino apenas a utilização de SSL, que controlará a criptografia dos dois lados.