How does this thought experiment not rule out black holes? How does the following brief thought experiment fail to show that general relativity (GR) has a major problem in regards to black holes?
The full thought experiment is in my blog post. The post claims that GR violates its own equivalence principle at the horizon of a black hole. The principle says that the laws of physics in any sufficiently small, freely falling frame are the same as they are in an inertial frame in an idealized, gravity-free universe. Here's a condensed version of the thought experiment:

In an arbitrarily small, freely falling frame X that is falling through the horizon of a black hole, let there be a particle above the horizon that is escaping to infinity. A free-floating rod positioned alongside the particle and straddling the horizon couldn't be escaping to infinity as well, or else it'd be passing outward through the horizon. However, if instead the rod didn't extend as far down as the horizon, then in principle it could be escaping, possibly faster than the particle beside it. In an inertial frame, unlike in X, a body's freedom of movement (in principle and if only relative to other free objects in the frame) doesn't depend on the body's position or extent. Then a test of the laws of physics can distinguish X from an inertial frame. If X was equivalent to an inertial frame, I wouldn't be able to tell whether the rod could possibly be passing the particle in the outward direction, by knowing only whether the rod extends as far down as an imaginary boundary (the horizon) within the frame. If X was equivalent to an inertial frame, the rod could in principle be passing the particle in the outward direction regardless of its extent within X.

The thought experiment above takes place completely within X, which is arbitrarily small in spacetime (arbitrarily small both spatially and in duration). That is, the experiment is completely local. That the particle is escaping to infinity is a process occurring within X; it tells us that the particle won't cross the horizon during the lifetime of X. The particle needn't reach infinity before the experiment concludes.
It isn't necessary to be able to detect (by some experiment) that a horizon exists within X. It's a given (from the givens in the thought experiment) that a horizon is there. Likewise, I am free to specify the initial conditions of a particle or rod in relation to the horizon. For example, I am free to specify that the rod straddles the horizon, and draw conclusions from that. The laws of physics in X are affected by the presence and properties of the horizon regardless whether an observer in that frame detects the horizon.
It seems to me that the only way the equivalence principle is satisfiable in X is when in principle the rod can be escaping to infinity regardless of its initial position or extent in X, which would rule out black holes in a theory of gravity consistent with the principle. Otherwise, it seems the bolded sentence must be incorrect. If so, how? In other words, how can I not tell whether the rod can possibly be passing the particle in the outward direction, by knowing only whether it extends as far down as the horizon?
I'd appreciate hearing from Ted Bunn or other experts on black holes. A barrier to getting a satisfactory answer to this question is that many people believe the tidal force is so strong at the horizon that the equivalence principle can't be tested there except impossibly, within a single point in spacetime. An equation of GR (see my blog post) shows that a horizon isn't a special place in regards to the tidal force, in agreement with many texts including Ted Bunn's Black Hole FAQ. In fact the tidal force can in principle be arbitrarily weak in any size X. To weaken the tidal force in any given size X, just increase the mass of the black hole. (Or they might believe it's fine to test the principle in numerical approximation in a frame larger than a point, but not fine to test it logically in such frame anywhere. Kip Thorne disagrees, in a reference in my blog post.) Note also that the Chandra X-ray Observatory FAQ tells us that observations of black holes to date aren't confirmations of GR, rather they actually depend on the theory's validity, which is to say the existence of black holes in nature isn't proven.
Edit to add: I put a simple diagram, showing GR's violation of its own EP, at the blog post.
Edit to add: I'm awarding the bounty to dbrane, whose answer will likely retain the lead in votes, even though it's clearly incorrect as I see it. (In short, the correct answer cannot be that an infinitesimally small frame is required to test the EP. It is in fact tested in larger labs. The tidal force need only be small enough that it doesn't affect the outcome. Nor is the horizon a special place in regards to the tidal force, says GR.) I do appreciate the answers. Thanks!
Edit to add: this question hasn't been properly answered. The #1 answer below made a false assumption about the question. I've beefed up the question to address the objections in the answers below. I added my own answer to recap the objections and reach a conclusion. Please read the whole post before answering; I may have already covered your objection. Thanks!
 A: Dbrane's answer contains the essential points. However I should point out that General Relativity is more sophisticated than your models suggest.


*

*The Inertial Frame concept (as used in the Equivalence Principle) is really only valid infinitesimally (whence it matches Minkowski space and "idealised gravity-free universe"). Some authors have critized the EP for this, and you are too. Most authors accept this and just present the EP "locally" - with "local" meaning no large deviations via curvature. Near the Event Horizon of a Black Hole is not a good place to find such flatness - especially if the BH is rotating - so we would be dealing with small Frames at best. All this makes "Law K" in your post suspect. (EDIT ADD FOR CLARITY) Thus the Blog phrase "Then law K is false in X" needs to say "Then law K is false in General Relativity".

*A different problem here is the status of "Event Horizon" (presumed at R=2M in your post). Put simply Event Horizons are difficult to find for an active Black Hole (one that is still eating up matter): its position is actually mobile until the Black Hole finally settles down (at the end of the Universe). This is a very counterintuitive behaviour of Black Holes and of General Relativity and arises because the "M" in "R=2M" hasnt been determined until the Black Hole has stopped growing!

*Concerning this:

In an inertial frame, unlike in X, a body's freedom of movement (in principle and if only relative to other free objects in the frame) doesn't depend on the body's position or extent.

The "freedom of movement" that I think you are referring to whether the object can be accelerated beyond the speed of light, which cannot be done in any Inertial Frame. As it cannot be so accelerated then no physical process in momentarily passing frame X can stop the momentarily straddling rod from entering the Event Horizon (remember that the Frame X is entering the Horizon too).
A: The answers to this question all get the answer wrong. The answer is that an accelerating frame has exactly the same horizon as the black hole, so that the equivalence principle holds. It does not hold infinitesimally as you approach the horizon, it holds including the horizon, if you identify the black hole horizon with the Rindler horizon.
The length scale at which the EP fails is the inverse curvature, which is as large as you like compared to the distance to the horizon. So the motion of the ball and the rod is the same in a uniformly accelerated frame as it is next to a black hole.
This type of equivalence principle, with a short distance to the horizon, was never used by Einstein, but it's sort of folklore by now!
LATER EDIT: I see that this answer might be interpreted as lending support to the claimed violation of the equivalence principle in the OP's question. There is absolutely no violation of the equivalence principle, and this can be easily seen.
Given a rigid rod L in the horizontal direction, it is impossible to accelerate it horizontally while keeping it rigid with an acceleration any greater than
$a_{\mathrm{max}} = c^2/L$
because then the left-most point would be past the Rindler horizon of the right most point. If you try to do this to a rod, it gets properly longer, because the acceleration on the left point can't keep up (this is easily seen in a space-time diagram). The intuition that fails is that there is such a thing as "uniform acceleration of a rigid rod". So when the rod is longer than the distance to the horizon it will not be able to pass the particle in the inertial frame before the whole frame reaches the horizon and the question is moot.
More generally, it is impossible to find a contradiction between a black hole horizon and the EP, because the near horizon metric is Rindler, up to curvature corrections which are arbitrarily small, so it is equivalent to a flat space, and there is no thought experiment which can refute this in a black hole which doesn't work in flat space just the same.
A: You're choosing a "freely falling" inertial frame. There's a natural set of coordinates for a non rotating black hole for this called "Gullstrand-Painleve" coordinates. They correspond to the natural coordinates for a particle falling into a black hole from infinity. See the wikipedia article.
In these coordinates, the speed of light is different for light trying to move away from the black than light moving towards it. As the little patch enters the black hole, the speed of light moving away from the black hole becomes negative, that is, even light moving away from the black hole still gets sucked into the singularity.
A well written, sort-of introductory and very intuitive paper you might find enlightening on these coordinates, and their generalization to a rotating and/or charged black hole, is:
Am.J.Phys.76:519-532,2008, Andrew J. S. Hamilton, Jason P. Lisle , The River Model of Black Holes
http://arxiv.org/abs/gr-qc/0411060
A: I just read your blog post and it's clear to me where you've gone wrong.
The equivalence principle only allows you to transform to an inertial frame locally. This means that if your spacetime is curved, then the falling observer can only choose Minkowski coordinates for an infinitesimal region around her. 
Think of a curved surface and having to choose a very small patch on it for it to appear flat. Clearly, you can't extend that flat patch indefinitely and call it an inertial frame of infinite extent (which you require in order to argue that the frame would allow you to send signals out to infinity).
The horizon is a global object that you realize exists when you patch together all the infinitesimal coordinate systems and examine its causal structure.
So, yes, the falling observer can do experiments to realize the horizon exists, but this does not violate the Equivalence Principle because such experiments are not done locally in an infinitesimal region. This applies to the rod that you seem to want to send away to infinity after crossing the horizon too. The infinitesimal flat patch in which you're allowed to play with the EP does not include infinity (or anything beyond the horizon), so you can't throw things outside of the horizon once you've crossed. 
A: Saggitarius A* has been confirmed to be a black hole, and many others have been discovered; by observing the movement of stars around Saggitarius A* over many years , ballistic trajectories for stars that can only be explained by a DEEP gravitational well (millions of solar masses) exerting a major influence in what appears to be an empty spot.  It is useful to remember that the existence of black holes has been confirmed by Astronomers, and that if your thought experiment somehow precludes their existence, the problem lies with your thinking.
I think the biggest issue you're having is with your treatment of this "rigid rod" as something that could actually physically exist.  Any rod in this universe is made up of atoms, and its rigidity and elasticity are entirely the result of electromagnetic forces between the atoms in the rod.  Therefore, saying that the "rod" is half-inside and half-outside the event horizon is only saying that half of the rod's constituent atoms are inside the event horizon and the other half are outside of it.  The rod that you call upon in your thought experiment seems to have properties that are not of this universe.
The EH is not a physical boundary, and if the black hole is large enough, tidal forces will be negligible on infalling matter when crossing the EH.  From the reference frame of the infalling matter, it would not experience being instantaneously teleported from one side of the EH to the other nor any of the other effects you've suggested.  The matter will continue on a ballistic trajectory orbiting the center of mass; a ballistic trajectory that will never take it outside of the horizon (by definition), sure, but upon crossing the horizon - if our object was a guy in a space suit - he'd have no indication that he'd crossed the event horizon (except perhaps that his radio to home base has stopped working). 
Importantly, the astronaut (or the rod) would not be stretched into infinity or torn apart at the EH; a black hole was recently discovered that has a radius of 4 light-days, and a density that is FAR below the density of Earth's atmosphere at sea level, for example.  Our astronaut would pass the horizon of that black hole sedately, and asphyxiate and die and freeze before ever encountering any forces strong enough to cause even mild discomfort, even at Voyager-1 speeds headed directly at the singularity.  
A: As this is a Bounty question (and because my other answer has a long set of comments) I have decided to add another answer. This answer is somewhat different from other answers provided, although it is consistent with them. There has been some challenge to understanding the other answers, and there may be some difficulty in understanding this answer too, but I shall record it here for those interested in this physical scenario.
In short: there is a contradiction in this physical scenario. The nature of this contradiction and its consequences I shall discuss at the end.
Let us consider the two physical assumptions which make up the scenario:
(A) A particle on a trajectory starting just above an Event Horizon, this trajectory being a timelike trajectory leading to timelike infinity (in an asymptotic model, say);
(B) A rigid rod (of length L say) straddling ie "half-in" and "half-out" of the Event Horizon at some time t say (in some appropriate coordinates).
The scenario continues by discussing Frames and so on, but this answer does not depend on anything else. Let us examine each of these assumptions a little more carefully.
(A) Is it possible for such a trajectory to exist? It depends on the Black Hole metric, but for the Schwarzchild metric if the particle has energy greater than some minimum E(R), then it may escape the region. If its energy and angular momentum is less than this value, it may orbit the Black Hole, or may directly plunge in. So let us assume that we are dealing with a Schwarzchild metric and that the particle can be given sufficient energy to follow the escaping trajectory.
Now let us consider (B) in more detail:
Is (B) possible? I claim that (B) is an inconsistent assumption. I shall outline a proof below.
First we need to return to the trapped surface property of an Event Horizon: a particle P is inside an Event Horizon if every trajectory leads to the Singularity. So now consider the rod. This rod is "rigid" in some sense, although we do not require any properties of "rigid" in this proof - so it could be (normal matter) elastic. However it is simpler to assume a regular model of a rigid rod of length L (much smaller than R=2M, say). Consider two points on the rod at time t: P is inside the Event Horizon and Q is outside. Since Q is outside there exists, by definition, some trajectory $\gamma$ such that $\gamma$ does not lead to the Singularity.
Now let the rod trajectory be such that point Q follows the $\gamma$ trajectory. The point P necessarily will follow a trajectory leading to the Singularity and so the proper distance PQ will extend to at least R = 2M in finite proper time. Thus the rod will break, and so the rod was not rigid as assumed but composed of at least two separate components (this is Hawking radiation!). So we have a contradiction as we assumed that the rod was rigid. So assumption (B) is inconsistent with General Relativity and cannot be used in any thought experiment.
A first objection might be via a "fluid model" intuition of the Event Horizon which allows a rod to be outside, then part straddling, then maybe entirely contained in the "fluid". But this intuition is not valid here: either the rod is or is not in the Event Horizon.
A second objection might be that this implies that the Event Horizon (fluid) has "moved" superluminarily, and this is not possible. The explanation is that the Event Horizon is not a local physical object and not constrained by the restrictions of Special Relativity. In fact it is a Global General Relativity object with counterintuitive properties: discontinuity and achronicity (see Hawking and Ellis 1973) and, as shown here, superluminarity.
We can now understand in outline the paradox that the original question identified with Inertial Frames. These are local objects in which a Global GR entity was analysed - but any attempt to account for the behaviour of a global object by purely local analysis will result in the sort of contradictions and paradoxes that the question has uncovered.
EDIT ADD FOR CLARITY:
There is a further objection to the stark conclusion of this answer, that can be understood in terms of further thought experiments. I shall discuss these and how they relate to the original question.
Let us assume that the rod is actually a long spacecraft with a removable capsule at the top. If the lower part of the spacecraft is within the EH, then the capsule might be fired off, escaping to infinity. Thus in this case it is not true that the entire spacecraft either is or is not contained within the EH, and the EH fluid model somewhat applies. Of course then the rod is not actually rigid as we assumed, so our conclusion is still valid, but only just. We could generalise this scenario to a spacecraft with N modules. A further generalisation simply assumes that the matter of the rod is such that at any distance along its length an explosion can occur (perhaps caused by a striking antiparticle) which would cause the rod to split and the top part to escape (to infinity). In this case (and within the modelling approximation) it would be appropriate to consider a fluid-like  model for the EH and thus talk about the rod "straddling" the Horizon.
However this "straddling" model assumes a wider physical scenario than did the original thought experiment, which merely considered the rod as an inert object, and certainly did not consider explosions, the quantum matter in the rod, and colliding particles which might happen (occasionally) in realistic physical situations. When these other factors are present one can discuss "straddling" rods: in the bare model as presented the "straddling" concept becomes inconsistent as discussed.
So in this wider sense the answer to the part of the thought experiment about how the upper straddling rod could in principle be detected in frame X apparently escaping to infinity faster than a nearby particle, is that experiments in X will have detected that the rod has been in some form of explosion near the EH (unlike any non-EH straddling rod which happened also to be escaping). However the original thought experiment was so limited (to a rigid rod idealisation) that "explosions" and the like cannot occur; as a consequence "straddling" cannot occur either.
A: I also would like to point out that the notion of "escaping to infinity" violates the locality of the equivalence principle, as it requires an infinite amount of time.  That, too, is not a local probe of the gravitational field, as it depends on all the dynamics of the spacetime between the probe point and the time the particle reaches infinity.
A: As far I understand the physics, in the local free fall frame, this is just an accelerating rod. In order to get away the from event horizon, the rod needs to accelerate heavily and continuously. If both ends of the rod accelerate with the same acceleration, then the rod will break due to length contraction. In order to keep the rod the same size, the back end has to accelerate more. That is just normal Relativity.
Assuming the front end of the rod accelerates just enough to stay ahead of the event horizon, it will eventually make it to infinity. If the back end of the rod accelerates enough to keep the rod intact, it will also make it out. If not, the rod will break, and the event horizon will catch up with the back end.
A: It is impossible to have part of the rigid rod being under the horizon and part above.
Mathematically on the horizon itself the speed of rod's movement becomes the speed of light. This means the linear contraction of length of the rod to zero for a stationary observer. Thus the rod crosses the horizon WHOLE AT ONCE and after this moment its speed becomes greater than speed of light.
Of course this also means that the rod cannot be made of substance or carry any information since information cannot be transferred faster than light (in actual world the BH will evaporte earlier than any object can approach the horizon, to cross the horizon one would have to move towards it faster than light with only light rays in theory can reach the horizon exactly at the last moment of the BH's existence).
A: The answer by dbrane nearly says what I am going to say but not as clearly and shortly as I will.  
The OP states the Equivalence Principle as
« The principle says that the laws of physics in any sufficiently small, freely falling frame are the same as they are in an inertial frame in an idealized, gravity-free universe. »
This is wrong.  This mistake has nothing to do with back holes, it's always wrong for any neighbourhood no matter how small it is.  It's only true for a point, not for a neighbourhood.  Or, to put it another way, it can be approximately true, up to first order, in a sufficiently small neighbourhood.  But it can never be exactly true except at a point (unless the gravitational field is of a rather special kind, and even the Earth's field makes this impossible).
Mathematically, the values of the Christoffel symbols can be zeroed out at one point by an apropriate choice of coordinates, but they cannot be made zero for a neighbourhood no matter how small it is.
What the principle of equivalence says is that you cannot tell the difference between a gravitational field and a pseudo-force due to your choice of coordinates.  It does not say you can find coordinates that makes the gravitational force zero.  But you can find coordinates that make it zero at one point.
Now although I know nothing about black holes, I have to point out that if you fix what level of approximation you desire, and choose a small neighbourhood which is sufficiently small that within that tolerance there is a frame which is close to being an inertial frame, the required smallness of the neigbhourhood might change with time.  With very violent dynamics, the needed smallness might shrink indefinitely, and if there were a singularity, it might be the case that no degree of smallness was sufficient for the wished for tolerance, and this would not violate the EP.
