My company support Android on their Exchange server, but they have policies (lockout, and password policies) that get applied to my phone. Are these permanent, or can they be removed later if I stop using the service?
No, they are not. For as long as you have the account registered in your email app, the policies are applied, however, if you remove the email account then the policies will no-longer be enforced.
The app is given a "device administrator" status (you can see any apps which have this in "Security" in your settings), and you can revoke that at any time. Revoking it, will of course, cause your email to stop working.