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$" 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 to enumerate the integral points. (See William Stein's answer in joro's first link for a description of the various implementations of this.) 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 algorithm for determining a basis for the Mordell-Weil group which has been provenunconditionally proven to terminate with the correct answer. I consider this theThis is a central problem inrelated to BSD and the arithmeticfiniteness of elliptic curvesSha. 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 complexityThere are conditional algorithms that assume finiteness of computingSha, or the Mordell-WeilBSD rank should beconjecture. It's somewhere between "not much easier than determiningAssuming GRH usually helps speed up finding upper bounds on the number of prime factorsrank in both cases. For rank at least $2$, we don't have a great way of finding rational points like the conductor" and "not computable"Heegner point construction for rank $1$.
Hindry wrote a great paper 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.
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". Of course these are both extremes, the complexity is probably closer to $N^{1/2 + \epsilon}$ where $N$ is the conductor.
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.