jmc

Let $$S=\sum _{i=1}^k(a_i+b_i).$$Since the $a_i$ and $b_i$ are all distinct, $$S\ge 1+2+\cdots +2k=\frac{(2k)(2k+1)}{2}=k(2k+1).$$Since the $k$ sums $a_1+b_1,$ $a_2+b_2,$ $\dots ,$ $a_k+b_k$ are all distinct and less than or equal to 2009, $$S\le (2010-k)+(2011-k)+\cdots +2009=\frac{(4019-k)(k)}{2}.$$Hence, $$k(2k+1)\le \frac{k(4019-k)}{2}.$$Then $$2k+1\le \frac{4019-k}{2},$$so $k\le \frac{4017}{5},$ which means $k\le 803.$

The 803 pairs $(1,1207),$ $(2,1208),$ $\dots ,$ $(401,1607),$ $(402,805),$ $(403,806),$ $\dots ,$ $(803,1206)$ show that $k$ can be 803. Thus, the maximum value of $k$ is $\boxed{803}.$