Answer:
   
   There are two aspects to the question: permissible and possible.
   
   Such a marriage is not permissable, even if the woman has an Orthodox
   "get". In extenuating case-by-case basis, it might be possible to
   prove the previous marriage never occured (for example, if the
   witnesses were not valid). Thus, one would have to consult a rabbi to
   be sure, but in most cases, the answer is that they may not get
   married. The circumstances of the divorce don't matter either.
   
   R' Nachman of Breslov suggests that the reason is that divorce is an
   act of separation. A student of Aaron, the first kohein, is described
   as one who "loves peace, pursues peace, loves people, and brings the
   close to Torah." Bringing the anger that divorce produces into his
   home would make this quite difficult. The source of the prohibition is
   Leviticus 21:14.
   
   Another reason is that a kohein may not marry someone with a
   premarital sexual history. In practice, a rabbi may be able to bring
   up enough legitimate doubt about one's kohein status to allow the
   marriage to occur. Conservative Rabbis routinely dismiss any family's
   belief that they're kohanim when this kind of need arises. Orthodoxy
   would demand leg work and evidence, and therefore can only do this
   when there are grounds.
   
   Is it possible? Yes. Such a wedding, while prohibited, does produce a
   halachically recognized marriage. The couple are obligated to divorce.
   However, they must divorce; it's not grounds for anulling the marriage
   as never having occurred. The children of such a marriage would be
   "chalalim", and have the status of a non-kohein.
   
   In a related vein, one might ask whether Kohainim may divorce. The
   answer is yes, however, the process is made more complicated. In
   normal cases of divorce, if you regret the decision before marrying
   someone else, you can remarry. (You can't remarry your ex if you were
   married in the middle. Otherwise there'd be a huge loophole allowing
   wife-swapping via quicky divorce.) However, a kohein could never
   remarry his ex-wife, so we want to make sure no mistake is being made.