You don't have to orbit, you can just use a rocket to stay put. All observers that can communicate with infinity for all time agree about the infalling object. It gets frozen and redshifted at the horizon.
EDIT: in response to question
The issue of two objects falling in one after the other is adressed in this question: How does this thought experiment not rule out black holes? . The answers there are all wrong, except mine (this is not an arrogant statement, but a statement of an unfortunate fact).
When you are near a black hole, in order to stay in place, you need to accelerate away from the black hole. If you don't, you fall in. Whenever you accelerate, even in empty Minkowksi space, you see an acceleration event horizon behind you in the direction opposite your acceleration vector. This horizon is a big black wall that follows you around, and you can attribute the various effects you see in the accelerating frame, like the uniform gravitational field and the Unruh radiation, to this black-wall horizon that follows you around.
When you are very near a black hole, staying put, your acceleration horizon coincides with the event horizon, and there is no way to tell them apart locally. This is the equivalence principle, in the form that it takes in the region by the horizon where there is no significant curvature.
The near-horizon Rindler form of the metric allows you to translate any experiment you can do in the frame near a black hole to a flat space with an accelerating observer. So if you measure the local Hawking temperature, it coincides with the Unruh temperature. If you see an object fall and get redshifted, you would see the same thing in empty space, when accelerating.
The point is that the acceleration you need to avoid falling in is only determined globally, from the condition that you stay in communication with infinity. If you stop accelerating so that you see the particle cross the horizon, the moment you see the particle past the horizon, you've crossed yourself.
You need to be a lot more careful when you use the phrase red-shift, due to how frequency is measured in general relativity. Roughly speaking, a photon is characterised by its wave vector $k$, which is a light-like four vector. The frequency measured by an observer is $g(\tau,k)$ where $g$ is the metric tensor, and $\tau$ is the unit vector tangent to the observer's world-line.
A little bit of basic Lorentzian geometry tells you that for any given photon $k$, instantaneously there can be observers seeing that photon with arbitrary high and arbitrarily low frequency.
So: start with your space-time. Fix a point on the event horizon. Fix a photon passing through that space-time event. For any frequency you want to see, you can choose a time-like vector at that space-time event that realises that frequency. Now, since the vector is time-like and the event horizon is null, the geodesic generated by that vector must start from outside the event horizon and crosses inside. Being a geodesic, it represents a free fall. So the conclusion is:
For any frequency you want to see, you can find a free falling observer starting outside of the black hole, such that it crosses the event horizon at the given space-time event and observes the frequency you want him to see.
So you ask, what is this whole business about gravitational red-shift of Schwarzschild black holes? I wrote a longer blog post on this topic some time ago and I won't be as detailed here. But the point is that on the Schwarzschild black holes (and in general, on any spherically symmetric solution of the Einstein's equations), one can break the freedom given by local Lorentz invariance by using the global geometry.
On Schwarzschild we have that the solution is stationary. Hence we can use the time-like Killing vector field* for the time-translation symmetry as a "global ruler" with respect to which to measure the frequency of photons. This is what it is meant by "gravitational redshift" in most textbooks on general relativity (see, e.g. Wald). Note that since we fixed a background ruler, the frequency that is being talked about is different from the frequency "as seen by an arbitrary infalling observer".
(There is another sense in which redshift is often talked about, which involves two infalling observers, one "departing first" with the second "to follow". In this case you again need the time-translation symmetry to make sense of the statement that the second observer "departed from the same spatial point as the first observer, but at a later time.)
It turns out, for general spherically symmetric solutions, there is this thing called a Kodama vector field, which happens to coincide with the Killing vector field on Schwarzschild. Outside of the event horizon, the Kodama vector field is time-like, and hence can be used as a substitute for the global ruler with respect to which to measure red-shift, when the space-time is assumed to be spherically symmetric, but not necessarily stationary. Again, this notion of redshift is observer independent. And it has played important roles (though sometimes manifesting in ways that are not immediately apparently related to red-shift, through choices of coordinates and what-not) in the study of dynamical, spherically symmetric gravitational collapse in the mathematical physics literature.
To summarise:
If you just compare the frequency of light measured (a) at its emission at the surface of the star in the rest frame associated to the collapse and (b) by an arbitrary free-falling observer, you can get basically any values you want. (Basically because the Doppler effect depends on the velocity of the observer, and you can change that to anything you like by choosing appropriate initial data for the free fall.)
One last comment about your last question:
You asked about what happens in the interior of the black hole. Again, any frequency can be realised by time-like observers locally. The question then boils down to whether you can construct such time-like observers to have come from free fall starting outside the black hole. By basic causality considerations, if you start with a time-like vector at a space-time event inside the black hole formed from gravitational collapse, going backwards along the time-like geodesic generated by the vector you will either hit the surface of your star, or exit the black hole. Though precisely how the two are divided depends on the precise nature of the gravitational collapse.
I should add that if you use the "global ruler" point of view, arguments have been put forth that analogous to how one expects red shift near the event horizon, one should also expect blue shifts near any Cauchy horizon that should exist. This has been demonstrated (mathematically) in the Reissner-Nordstrom (and similar) black holes. But as even the red-shift can sometimes run into problems (extreme charged black holes), one should not expect the statement about blue shifts near the Cauchy horizons to be true for all space-times.
Best Answer
Consider the non-relativistic problem of a particle falling into a potential well and releasing all its energy in there. The quantity which is conserved during the infall is the total energy $E = T + V + E_{internal}$, where $T$ is kinetic energy, $V$ is the potential energy, and $E_{internal}$ is some internal "chemical" energy of the particle.
Now we assume that the particle starts at rest at infinity where the potential is zero so that $E = 0 + 0 + E_{internal} = E_{internal}$. As the particle starts falling to the potential well, nothing happens to internal energy, $V$ becomes negative and since energy is conserved, that must be countered with a positive $T$. When we arrive all the way in the potential well, no matter what happens with the kinetic and potential energy, we always have $E= E_{internal}$ and when the energy release in the well comes about, it is exactly $E= E_{internal}$ which is released.
You can think similarly about the black hole along with the realization that $E_{internal} = m_0 c^2$, where $m_0$ is the object's rests mass. In other words, if a particle of (rest) mass $m_0$ falls into a stationary black hole starting at rest at infinity, the black hole will receive exactly $m_0 c^2$ in terms of energy, no matter what happens to the kinematic or potential parts of the energy.
EDIT
Of course, the full relativistic problem has to be considered more carefully. First of all, what is exactly the mass of a black hole? One of the postulates of relativity is that a freely falling observer never feels gravity - so a freely falling observer will judge the black hole to be probably weightless and thus there cannot exist any local, frame-independent notion of the black hole mass. The black hole mass must be, in fact, defined by some coordinated measurements of privileged observers.
Furthermore, notice that no frame is privileged and thus there is no notion of big or small velocity! To define a notion of velocity, you also need a privileged frame with respect to which you are measuring it!
Sometimes it so happens that the black hole is in such a state that there exists a family of observers at infinity who collect measurements in which the black hole field appears as stationary. In such a case, we call the black hole stationary and the time in which these observers measure any physical process will be our privileged notion of time throughout the space-time.
It is also these observers through which we define the notion of mass. Since they define a notion of rest and the space-time around them is almost flat, they feel the gravity of the black hole in the weak-field, Newtonian limit. The mass of the black hole is defined exactly and only as the apparent Newtonian mass $M$ in the $\approx -M/r^2$ gravitational force these observers at infinity feel. In other words, you could understand the mass more as total gravitating energy as felt by observers at infinity.
Since the background is stationary with respect to this time, there will be a respective integral of motion for the evolution of test bodies moving in this space-time due to Noether's theorem. This integral is the temporal component of four-momentum $p_t$. Now, at infinity the space-time is asymptotically Minkowski space-time and if the test particle starts there at rest, we will just have $p_t = -m$ and other component of four-momentum equal to zero.
As the particle then falls into the black hole, $p_t = -m$ will never change and will play exactly the same role as $-E$ in the argument given above. Similarly, the growth of coordinate velocity (as measured by the observers at infinity) as a compensation of some kind of potential energy can also be traced to the conservation of $p_t$, at least in the Newtonian limit.
Of course, one could argue that this does not automatically make $-p_t$ the contribution to the black hole mass once the particle is absorbed by the central, mathematically ill-behaved singularity. It is an elegant and favorable candidate, because the sum of $-p_t$s from many particles should not be possible to annihilate by Noether's theorem and by some kind of assumption of adiabaticity of the black hole growth, so the $-p_t$ must go "somewhere". But this just tells us that the contribution to the black hole should be a linear function of $-p_t$.
The argument why it is exactly $-p_t$ to increase the black hole mass can come only from the consideration of the infalling body as a non-test object, that is an object which perturbs the black hole background with its own gravitational field. From such arguments we know that a part of the infalling energy almost always gets radiated away by gravitational radiation, but if the body gets sufficiently light, the contribution of mass to the resulting black hole indeed converges to $-p_t$.