The following seven pairs add to $16$ so at least one of each pair must be removed:

$(1,15)$, $(2,14)$, $(3,13)$, $(4,12)$, $(5,11)$, $(6,10)$, $(7,9)$.

If removing these seven is sufficient, then we would be left with $8$, $16$ and seven others.

But

$16+9 = 25$
So we must remove $9$ and keep its partner
$7$

$7+2 = 9$
So we must remove $2$ and
keep $14$

$14+11 = 25$ So we
must remove $11$ and keep $5$

$5+4 = 9$
So we must remove $4$ and keep
$12$

$12+13 = 25$ So we
must remove $13$ and keep $3$

$3+1 = 4$
So we must remove $1$ and keep
$15$

$15+10 =
25$ So we must remove $10$ and
keep $6$

But we have kept $3$ and
$6$ which add to $9$.

Hence it is not
sufficient to remove only seven. If we remove the number $6$, we
obtain a set which satisfies the condition:
$\{8,16,7,14,5,12,3,15\}$ or in ascending order
$\{3,5,7,8,12,14,15,16\}$.

Hence eight is the
smallest number of numbers that may be removed.

*This problem is taken from the UKMT Mathematical Challenges.*