Many astronomers think that the moons of Mars, Phobos and Deimos, are captured asteroids. Others object precisely because of the issues that you raised. Capture is not easy. Sans a collision, capture is impossible in the Newtonian two body problem. A hyperbolic trajectory stays hyperbolic. On the other hand capture in the multi body problem can happen.
A simple way to look at the three body problem is via a patched conic approach. One ignores the secondary (the planet) when the object to be captured is outside the secondary's sphere of influence, and then ignores the primary (the sun) when the object is inside the sphere of influence. Behavior inside the sphere of influence simplifies to the two body problem. Since orbital energy is constant in the two body problem, capture once again appears to be impossible.
The problem is that switching from ignoring the secondary to ignoring the primary discards the subtle behaviors that lead to capture. The primary acts on the object throughout the encounter, and the secondary acts gravitationally on the object when it is well outside the sphere of influence. While a patched conic approach does yield a fairly good estimate of how a flyby (aka gravity assist) changes both the direction and magnitude of the primary-centric velocity vector, it gives a lousy picture of capture.
The planet-centered orbital energy of the object to be captured is constant in the two body problem. It is not constant in the three body problem. The osculating planet-centered orbital energy of the object to be captured is time varying in the three body problem. Under the right circumstances, the orbital energy can temporarily switch from slightly positive, meaning an escape trajectory, to slightly negative, meaning a temporarily bound orbit. Since gravity gradient from the sun is greatest when the planet is at perihelion, this is where capture is most likely to occur.
Capture is much more likely if the object to be captured enters the planet's sphere of influence near the sun-planet L1 or L2 point. This leads to all kinds of weird behaviors. One needs to know the concepts of stable and unstable manifolds to firmly understand what happens (and to be honest, my own understanding of these concepts is a bit unstable). The Hill sphere acts as an energy barrier to escape. The object will temporarily be trapped in the planet's Hill sphere when the encounter occurs near perihelion and the object enters the sphere of influence near the L1 or L2 point. The only way out is for the object's chaotic orbit to take the near the the L1 or L2 point.
We've seen this happen a number of times here on Earth. In fact, one such visitor, J002E3, most likely is the Apollo 12 S-IVB third stage. It probably left the vicinity of the Earth-Moon system via the Earth-Sun L1 or L2 point in late 1969 or 1970, and later found its way back home for a short while.
This is not true capture. Eventually the captured object's chaotic orbit will take the object near the L1 or L2 point, and then it's gone. Something else has to happen to turn that temporary capture into a permanent bound orbit. A number of mechanisms have been proposed for turning these temporarily bound orbits into permanent bound orbits. These include
An encounter with the planet's atmosphere,
Multibody interactions with the planet's moons,
An increase in mass of the planet,
Drag from the gas and dust in the protoplanetary disk.
The latter two can't happen now, but they could have happened when the solar system was still forming.
Collision is one way to avoid these problems. That is how the Earth's moon is widely believed to have formed. Per this giant impact hypothesis, a Mars-sized protoplanet slammed into the Earth shortly after the formation of the solar system was complete. Some of the ejecta went into low Earth orbit and eventually formed the Moon.
Some people are now thinking that this is how Phobos and Deimos formed as well. Now that we've had a better look at those moons, they don't quite look like asteroids. They look more like Mars itself.
People are now learning to take advantage of ballistic capture to reduce delta-V requirements for a spacecraft. A recent example is the Gravity Recovery and Interior Laboratory (GRAIL) experiment, which comprised a pair of satellites used to map the Moon's gravity field. This mission did not use Apollo-style transfer from a low Earth orbit after launch to a trans-lunar trajectory, and then six days or so later, transfer to a lunar orbit. These vehicles instead went to the Sun-Earth L1 point and from there followed a ballistic capture trajectory to the Moon. This reduced the required delta-V by a good amount.
The relationship between fuel costs and delta-V is highly non-linear; it's almost exponential. A small reduction in delta-V can reduce fuel costs by a good amount, or it can enable a larger payload. The latter was the case with the GRAIL experiment. Reducing the required delta-V meant they could reuse heritage instrumentation (the equipment used on GRACE) without a lot of changes. A direct trajectory would have necessitated a major redesign.