Flattening a nested map
A couple of things to try: 


You assemble a map at every level of nesting. It is probably quicker
to pass up sequences of key/value pairs.
Even the single entries return a map. We can cope with a
MapEntry directly using reduce instead of for.


We might end up with ... 

(defn flatten-record [record]
  (reduce
   (fn [a [k v]]
     (if (map? v)
       (into a (flatten-record v))
       (conj a (clojure.lang.MapEntry. (match-table k k) v))))
   []
   record))


I'm assuming it's quicker to build a MapEntry than a small vector or list. 

The above returns a sequence. We have to convert the product into a map:

(def example-input {:foo {:foo-host "host-1" :user {:foo-user "user-1" :foo-id "id-1"}}
                    :bar {:bar-var "potato"}})

(into {} (flatten-record example-input))
;{:host "host-1", :user "user-1", :id "id-1", :var "potato"}




The recursive call of flatten-recordis not in tail position, so neither recur nor trampolineare available.