I figured out a faster, more functional programming-oriented algorithm for this problem -- see below. Besides that, your code overall looks idiomatic and was easy for me to understand, so I have no real criticisms in that area.

zipmap

zipmap is ideal for concisely constructing maps like your code->letter map:

(def code->letter
  (zipmap (map str (iterate inc 1)) (map char (range 97 123))))

;=> {"1" \a, "2" \b, "3" \c, ... "26" \z}

One way to avoid using flatten

Personally, I think using flatten is fine, but some view it as being somewhat hacky, and I've heard it said that if you find yourself using flatten, there is usually a better way to do what you're trying to do. In this case, I would use mapcat -- it's like map, but it handily concatenates the results together into a single collection.

...
(mapcat (fn [[k v]]
          (when (.startsWith number k index)
            (possible-strings number (+ index (count k)) (str acc v))))
        code->letter))))

or,

...
(mapcat (fn [[k v]] (possible-strings number (+ index (count k)) (str acc v)))
        (filter #(.startsWith number (key %) index) code->letter)))))

Functional programming

You're correct in that your algorithm is not (and cannot be) tail-recursive. This is because you're wrapping the recursive call to possible-strings within a filtering and mapping operation. I'm not familiar with the term "backtracking algorithm," but it does seem appropriate in this case. This initially struck me as the kind of thing you would do with a reduce, building up a string from scratch, however, you do have to keep "backtracking" to build up new strings using different groupings of digits. I might be wrong about this, but I don't think this is something you can do with tail-recursion, which means you can't use recur and there would be performance implications, especially for large inputs.

Here's another approach: write a function that takes a number and returns a list of possible arrangements of numbers from 1-26. Then just map the numbers to letters and you'll have your possible strings.

This function, which I'll call possible-arrangements, is a little complicated to write. My approach is to walk through the number string from the beginning and form a tree, looking at numbers 2 at a time and branching off for each possibility, each branch terminating once it reaches a list of numbers that can't be broken down any further. For example:

; *starred numbers are ones that are evaluated to see if they can be broken
; down further

                  *4125    ; 41 is not in range, so only one possibility...
                    |
                  4 *125   ; 12 can be 1 2 or 12, so we branch, etc.
                    /  \
                 1 *25  12 5 
                   /\     |
                  /  \    |
      (4 1 ...) 2 5  25  12 5   = 4 1 2 5, 4 1 25, 4 1 12 5

; the result would be [["4" "1" "2" "5"] ["4" "1" "25"] ["4" "12" "5"]]

.

(defn possible-arrangements [^String n]
  (case (count n)
    1 [[n]]
    2 (let [each-digit (mapv str n)]
        (if (contains? code->letter n)
          [[n] each-digit]
          [each-digit]))
    (let [a       (str (first n))
          ab      (subs n 0 2)
          prepend (fn [x offset] 
                    (map (partial cons x) (possible-arrangements (subs n offset))))]
      (if-not (contains? code->letter ab)
        (prepend a 1)
        (concat (prepend a 1) (prepend ab 2))))))

(defn possible-strings [^String n]
  (for [nums (possible-arrangements n)
        :let [chars (map code->letter nums)]]
    (apply str chars)))

This is still not a tail-recursive solution, but it's about 4 times faster, I think because it isn't having to perform 26 string operations for each digit of the input number.