Does Coppersmith's method always finds non-trivial factor of integers of the form $n=a(2^k b+1)$ assuming $1 < a<2^k b +1$ and $b < n^{1/4-0.05}$? Got an argument and numeric evidence that pari's implementation
of Coppersmith's method finds non trivial factor of integers
of certain form under some assumptions very efficiently.
Three $5000$ bit integers were solved for a minute and half each.
The algorithm didn't fail for $100$ integers of size $500$ bits.
From pari's documentation for Coppersmith method

zncoppersmith(P, N, X, {B=N}): finds all integers x with |x| <= X such that 
  gcd(N, P(x)) >= B. X should be smaller than exp((log B)^2 / (deg(P) log N)).

Observe that this implementation might find nontrivial factor of $N$.
In general it is efficient, but certain choices of $N,X,B$ are significantly
slower than others.
For natural $k,a,b$, let $n=a(2^k b + 1)$.
Assume $1< a<2^k b +1$ and $b < n^{1/4-0.05}$
and $k$ is given. (The assumption that $k$ is given can be
dropped, since there are at most $\log_2{n}$ possibilities,
not affecting the complexity.)
The $0.05$ can be lowered, but this affects the running time
adversely.
Since $a<b$ we have $2^k+b > n^{1/2}$. In pari's implementation,
choose $P(x)$ linear $Ax+1$ and set $B=n^{1/2}$. We get $ X < n^{1/4-e_0}$
for real positive $e_0$, in our case $0.05$.
Setting $A=2^k$ and $b=x$, $P(x)=2^k x + 1$ is the second factor, and because
of the inequality the implementation will find $b$ and the non-trivial
factor. $\gcd(N,P(x))=2^kb+1$, satisfying the other inequality.
We can replace $2^k$ by sufficiently large known natural.

Q1 does Coppersmith method always finds nontrivial factor of $n$ of this
  form in polynomial time?

In case of negative answer to Q1:

Q2 How to explain the seemingly optimistic experimental results?

Sample session:
time n,b,cc=coppersmith1(2004);cc

log_2(N)= 5007
factor  35838357358...
Wall time: 1min 38s

Sample sage/pari implementation:
def coppersmith1(e):
    """
    coppersmith factorization for
    N=a (2^k b + 1), b< N^{1/4-0.05},a<2^k b+1
    |e| is $k$.
    to run:

    time n,b,cc=coppersmith1(2004);cc
    """
    B=2**e
    B2=2**(e//2)
    a1=randint(2,B2)
    a2=randint(B//4,B//2)
    q=next_prime(a2)
    N=q*(B*a1+1)
    pre=500
    gp.default('realprecision',pre)
    K.<x>=ZZ[]
    pol=B*x+1
    eps=0.05
    bou=round(N^(1/QQ(4)-eps))
    cc=gp.zncoppersmith(gp(pol),N,round(N^(1/(4)-eps)),round(N^(1/2)))
    cc=eval(str(cc))
    cc=[ZZ(_) for _ in cc]
    print 'log_2(N)=',round(RR(N).log(2))
    print '<?',a1<bou,'a1=',a1,round(RR(N^(1/4-eps)))
    for d in cc:
        di=B*d+1
        g=gcd(N,di)%N
        if g>1:
            print 'factor ',g,'<?',d<bou

    return N,B,cc

 A: Coppersmith's method is known to solve equations modulo $N$ or unknown divisor of $N$ if the wanted solution is small enough.
If I understood things correctly, here you have a modulus $n=a(2^kb+1)$ where you know $n$, and $k$. Therefore you can write the following equation $2^kx+1=0 \mod (2^kb+1)$ where $(2^kb+1)$ is an unknown divisor of $n$. Then if the bound for $x$ is small enough then you can solve through Coppersmith and recover $x=b$.
Specifically Coppersmith's method (see Theorem 6 of this resource on Coppersmith's method):

Let $N$ be an integer of unknown factorization, which has a divisor $b\geq N^\beta$. Furthermore, let $f_b(x)$ be an univariate, monic polynomial of degree $\delta$. Then we can find all solutions $x_0$ for the equation $f_b(x) = 0 \mod b$ with  $x_0 \leq\frac{1}{2}N^{\frac{\beta^2}{\delta}-\epsilon}$ in time polynomial in $(\log{N},\delta,\frac1\epsilon)$

Your equation is not monic, but since you know $2^k$ and that is coprime with $n$ you can invert and get $x+2^{-k}=0 \mod (2^kb+1)$. Now you just have to show your bounds satisfy the above theorem. 
In your case (assuming I grasp this correctly here), it seems that $\beta^2=\frac14$ and $\delta=1$,$\epsilon=e_0$ so the bound becomes $b\leq\frac12n^{\frac14-e_0}$.
It seems there is an additional $\frac12$ to conclude the proof. Either you address it in $e_0$ (making it $\log_N{2}$ smaller) or you apply Coppersmith two times in different intervals as done by May in Theorem 7.
