Pues a lo mejor no lo configuraste bien, en principio el K9 tiene soporte exchange para 2003 y 2007 pero por ejemplo si tu exchange esta dentro de un dominio de empresa ya no te lo pilla ni de coņa.
Por otro lado con el Email oficial algunos usarios que usan exchange si lo tiene configurado y funcionando, desconozco estas detalles ya que no uso exchange solo Gmail y Hotmail