First, I'd like to revisit Will Sawin's upper bound, but I make no promises about off-by-one errors (which I think I made in comments elsewhere on this page).  The product of any sequence of $x$ consecutive integers has $p$-valuation at least $\lfloor \frac{x}{p-1}\rfloor - \lfloor \log_p(x+1) \rfloor$.  The $p$-valuation of $\binom{n}{a}$ is the number of carries when adding $a$ to $n-a$ in base $p$, so this is bounded above by $\lfloor \log_p n \rfloor$.  In other words, the product of the $x = b-(n-a)$ integers from $n-a+1$ to $b$ must satisfy $\lfloor \frac{x}{p-1}\rfloor - \lfloor \log_p(x+1) \rfloor \leq \lfloor \log_p n \rfloor$.  Pushing some terms around yields the bound $$x \leq (p-1)\lfloor log_p(n) \rfloor +(p-1) \lfloor log_p log_p n \rfloor + 2p - 2.$$
If we only worry about making $\frac{n!}{a!b!}$ into a 2-adic integer instead of an ordinary integer, then this bound is sharp, since the case $n=2^k, a=2^k-1, b = 2^y-1$ saturates it when $k = 2^y-y-1$.

When $n$ is large, $(p-1) \lfloor \log_p(n) \rfloor > \lfloor \log_2(n) \rfloor$ for odd $p$, so this suggests that it is good to check 2-valuations when eliminating candidate triples.  By request, here is some computer code.

I couldn't find a fast function in SAGE for computing the valuation of a factorial, so I made a Cython file "val.spyx" with the code:

    def val(int a, int p):
        cdef int i,r
        i=0
        r=p
        while(a >= r):
            i = i + (a/r)
            r = r*p
        return i

In SAGE, I compiled it with 

    load ".../val.spyx"

where "..." indicates the directory holding the file (available with the "pwd" UNIX command).  Then I wrote three functions (I imagine there are more elegant ways to write these):

    def innerloop(a,b,c):
        r=0
        p=2
        while(r==0 and p <= min(b,c)):
            if val(a,p) < val(b,p) + val(c,p):
                r=1
            p=next_prime(p)
        return r

    def testvirtue(m,k):
        r=0
        for i in range((m+k+1)/2,m):
            if innerloop(m,i,m-i+k)==0:
                print m,i,m-i+k
                r=1
        return r

    def testrange(m,n,k):
        for i in range(m,n):
            if testvirtue(i,k):
                k=k+1
                testvirtue(i,k)
        return k

Anyway, starting with k=3 and running up to 80000 took about 2 hours on my laptop:

    10 7 6
    36 23 17
    36 29 11
    56 47 14
    100 59 47
    162 107 62
    162 110 59
    256 142 122
    256 202 62
    256 239 25
    256 241 23
    261 223 47
    261 239 31
    416 239 187
    1056 620 447
    2080 1214 878
    2080 1853 239 
    3201 1775 1439
    4384 2735 1663
    32778 18458 14335
    32808 18617 14207
    32808 23615 9209
    65536 34963 30590
    65536 39314 26239
    65536 39319 26234
    65536 39323 26230
    65536 39346 26207
    65536 39347 26206
    65536 52447 13106
    65536 39347 26207
    19
    
As you can see from the last entries, the optimal value of $a+b-n$ jumps by 2 to 18 at 65536.  I checked a few larger powers of two beyond 80000 - here are the maximal values of $a+b-n$:

    4 1
    8 1
    16 3
    32 3
    64 4
    128 5
    256 8
    512 8
    1024 9
    2048 8
    4096 11
    8192 14
    16384 14
    32768 14
    65536 18
    131072 17
    262144 20
    524288 20
    1048576 21
    2097152 12
    4194304 20
    8388608 20
    16777216 21

I couldn't find a really good pattern here, although powers of 4 tend to yield better values than odd powers of 2.  $2^{21}$ is very strange.