As Tsuyoshi Ito answers, when you modify a noun, you can put a genitive (の)-marked noun phrase, or a relative clause. Notice that 対する retains the morphological form of a verb (although it does not fully inflect as with real verbs). Thus, at least etymologically, you can consider the 対する-phrase as a relative clause.
[(それが)手紙に 対する (ところの)]返事
'a response [such that it aims against the letter]'
'a response that is aimed against the letter'
Here, the に phrase is an argument of the verb 対する. You cannot omit the verb and retain its argument. The (それが)手紙に in the following will be a strange syntactic object; it has an argument but not the predicate, and is still intended to function as a relative clause. That is why it is ungrammatical.
* [(それが)手紙に] (それが)手紙に ](ところの)返事
That is why it is ungrammatical.
If you want to say it short, you can use へ in front of the genitive case like this:
? 手紙 への 彼の返事
自分の中の彼 への 気持ち
彼 へ 気持ちをどう表すか
although the first example is awkward because へ can be used only against things that will be affected by the action.
In your last example, the に-phrase simply functions as an argument.
彼 に 気持ちをどう表すか