The growth of the Internet has been accompanied by the growth of e-services (e.g. e-commerce, e-health). This proliferation of e-services and the increasing regulatory and legal requirements for personal privacy have fueled the need to protect the personal privacy of e-service users. Approaches are needed to ensure that providers of e-services comply with the privacy policies of service users. In this paper, we examine privacy legislation to derive requirements for privacy policy compliance systems. We then propose an agent-based architecture for a privacy policy compliance system that satisfies many of the requirements and discuss the strengths and weaknesses of our proposed architecture.