GolfScript (6153 chars)
~2/),3>[1]]3>[2][1 3]]({2*:x;{:S{x<},{x\-S+.&}/}%}/{,}$.0=$0=n*
A major speed optimisation results from a bit of duplicate-trimming, at a cost of 3 chars:
~2/),3>[2][1 3]]({\,=2*:x;{:S{x<}+,{x\-S+.&$}/0={2*n}%.&}/{,}$0=n*
Online demo NB Let f(2n) be the size of the optimal set for [4..2n]. Then f(2n) <= f(2n+2) <= f(2n) + 1. The first inequality is obvious from the definition; the second is easily seen by taking any optimal set S_{2n} for [4..2n] and taking the union with {n+1}, or indeed with {2n+2-x} for any x in S_{2n}.
This suggests a greedy algorithm, which the first revision of this answer implements. However, that greedy algorithm turns out to be incorrect. The unique optimal set for [4..20] is {2,4,8,10}, which is not a subset of either of the two optimal sets for [4..26]: {1,3,7,11,13} and {2,4,8,12,14}.
My current solution assumes that every optimal set will contain only odd numbers or only even numbers. I haven't proven this, but given that odd + even = odd a set which mixes parities is wasting possible pairs.