LiveScript (179 chars), good running time

f=(s)->
  c=s.replace /[^A-Z]/g ''
  if c
    for i from 0 to 9
       if s.indexOf(i)<0&&a=f s.split(c.0).join i
         return a
  else
    if eval s.replace(/(^|\D)0+(\d)/g,'$1$2').replace \= \==
       return s


   
f("AA+DB=CC")

LiveScript (179 chars)

It has deterministic and relatively quick running time and works with other operators (+, -, *) as well.

f=(s)->                     # define function that takes parameter s
  c=s.replace /[^A-Z]/g ''  # remove all the non-letters
  if c                      # if any letters remain
    for i from 0 to 9       # loop from 0 to 9
       if s.indexOf(i)<0&&a=f s.split(c.0).join i  # if i is not present in the number, replace the first letter with i and call the function recursively
         return a           # if there is a solution, return it
  else                      # if there are no letters left
    if eval s.replace(/(^|\D)0+(\d)/g,'$1$2').replace \= \==  # if the expression is correct (we need to remove leading 0, because javascript interprets numbers with leading 0 as octal)
       return s  # return solution


   
f("CODE+GOLF=GREAT")