The best unconditional complexity bounds I know of are those coming from Baker's theory of linear forms in logarithms. Baker wrote a paper "[The Diophantine equation $Y^2 = aX^3 + bX^2 + cX + d$][1]" where he worked out some impractical but rigorous bound on the complexity of enumerating the integral points on an elliptic curve. I think that there better results on linear forms in logarithms that can improve this bound, hopefully someone will surface that can address this. Bharagava's algorithms for enumerating binary quartic forms could also help.

In practice, you almost never use Baker's method for computing integral points on elliptic curves. Usually one computes a basis for the Mordell-Weil group first and then uses the [GPZ algorithm][2] to enumerate the integral points. There should be some improvement in the complexity of GPZ coming from new results on linear forms in elliptic logarithms, but I'm not sure if anyone has really worked this out in detail.

The main problem with the GPZ approach is computing a Mordell-Weil basis in the first place. There is **no** algorithm for determining a basis for the Mordell-Weil group which has been **proven** to terminate with the correct answer. I consider this the central problem in the arithmetic of elliptic curves. It's also the main bottleneck in using GPZ to get a much better bound on the complexity the OP asked about.

I'm pretty clueless about what the true complexity of computing the Mordell-Weil rank should be. It's somewhere between "not much easier than determining the number of prime factors of the conductor" and "not computable". 

Hindry wrote a great [paper][3] about why computing the Mordell-Weil group is hard, and it's probably about the best place to get an idea of the complexity without getting the experience of computing a bunch of Mordell-Weil groups.

Computing ranks is still an art form. If you have a particular curve $E$ in mind, and you've tried E.gens() in Sage, MordellWeilShaInformation(E) in Magma, and looked for it at http://www.lmfdb.org, then it would be good to ask someone.


  [1]: http://jlms.oxfordjournals.org/content/s1-43/1/1.full.pdf
  [2]: http://www.inf.unideb.hu/~pethoe/cikkek/72_S_INTGPZ.pdf
  [3]: http://webusers.imj-prg.fr/~marc.hindry/MW-size.pdf