Is it safe to put a client's personally identifiable information on Microsoft's Office-365, or another Cloud provider storage?
Cloud services such as Office 365 can be far safer than using your own or a suppliers data centre facilities.
So yes, you can of course put client data on cloud services. But will they be happy? Hmm. And will you be meeting their regulatory requirements?
Well only you/they can answer that.
Look for security certifications related to the regulatory environment your client has to work in. Get buy in from the Information Owners by carefully explaining the benefits, risks and mitigations. Look for other similar organisations that may have followed the same journey. Check with relevant government agencies on their views.
BTW, Office 365 is particularly good at this. Their certifications are second to none and they have world class security processes. Microsoft really understand government and enterprise security requirements.
It depends on what regulatory requirements you have and whether the cloud hosting provider meets those standards. PII is not a standard, it's a classification of data. As a result, you won't find a cloud offering claiming to be PII Compliant.
Instead, determine the regulatory requirements you need to abide by (PCI-DSS, ITAR, HIPAA, GLBA, ISO27K, etc) and base your decision on whether the provider you're looking at complies with those standards.
You'll also need to determine whether you want dedicated hosting or shared hosting. In other words, some standards require dedicated hardware for your services and applications rather than shared-tenant hardware. Keep that in mind as it may affect your decision and definitely affects your cost.