Enterprise Architecture deals with the structure of an enterprise, relationships and interactions of its units. It provides a holistic approach to reconcile IT and Business concerns in an enterprise. Virtual Enterprises are collaborative ad-hoc alliances of multiple enterprises for a specific business opportunity. This paper looks into both the paradigms and Enterprise Architecture viewpoint of Virtual Enterprise. Service Oriented Architecture as a style of Enterprise Architecture proves to be an enabler of Virtual Enterprises at Business and Technology Levels. The three major challenges with Virtual Enterprise are flexibility, adaptability, and agility. This paper discusses Virtual Enterprise Architecture as a solution to these challenges, surveys research into formal models of Virtual Enterprise Architecture and identifies current gaps in this research.