Necesitas que alguien te pase el apk que está en system/app. Lo haría yo mismo pero el cliente email es de lo primero que me cepillo en cyanogen.
Cuando dices que no puedes agregar una cuenta exchange supongo que te refieres al menú de cuentas y sincronización verdad? Nunca he manejado nada relativo al exchange pero sobre las cuentas te diré que no todas las apps se integran con el gestor de cuentas y eso no impide que no puedas crear la cuenta desde la propia aplicación.
Para descartar que sea problema de haber borrado el cliente nativo te diría que te bajases alguna app para trabajar con exchange (puedes usar la versión trial del Touchdown) y comprobar si sigue fallando sincronización mientras esperas a que alguien te suba el apk.