TL; DR
This question has two parts which I address distinctly:
- How does the FTL communication in Star Trek work? - through what's called 'subspace', which is a form of space that exists alongside our space but doesn't seem to have the light-speed barrier, meaning messages can travel at far faster speeds than the speed of light
- How much faster is this than conventional warp? - it depends. If you have subspace boosters, we see speeds of Warp 9.9999 = 199,516 times the speed of light; obviously significantly faster than the speeds any 24th Century Starfleet vessel could attain. Without these boosters though, we see a speed somewhere between Warp 3 and Warp 4 on the TNG scale, so not really all that fast relatively. The other related point raised in the question is about the Warp limit being 9.9 - we see here that subspace messages can exceed this, however they still can't break the Warp 10 barrier (which is explained as infinite velocity). Hence, we still know that some speed barriers must apply.
I see this question as having two distinct parts which I will accordingly address distinctly:
1: How does FTL Communication in Star Trek Work?
As outlined in the other answers and on Memory Alpha, the communication used in Star Trek is called Subspace Communication. By sending messages over subspace, it means that faster-than-light communication can be used, as the light-speed barrier does not apply in subspace. The precise definition of subspace is somewhat elusive, however we know that:
Subspace is an integral part of the space-time continuum, distinct, yet coexistent with normal space. Subspace and normal space are confluenced together. However, in some regions an interfold layer forms between the two realms. (VOY: "Real Life") Subspace has an infinite number of domains. Geordi La Forge compared it with "...a huge honeycomb with an infinite number of cells". (TNG: "Schisms")
(Source)
This seems to be classic Star Trek technobabble to me; the fact is that we don't actually know all that much about Subspace, other than that it can be accessed to send messages through and that the light-speed barrier does not apply in it.
Now, for the more important part:
2: How much faster is it than warp?
As mentioned in the question, in TNG 'Where No One Has Gone Before', when the Enterprise-D is sent hurtling a vast distance into another galaxy, Data tells us how long it would take for a subspace message to travel. Maths time!:
- The Enterprise was ~2.7 million light years from their previous position
Now, I think it's reasonable to assume that the Enterprise-D's previous position was within real-time communication distance of Starfleet, so the distance between their previous position and Starfleet would be relatively negligible
From this information, we can calculate the approximate speed of a subspace communication. Bear in mind that there would be other factors involved which could distort this slightly; for the majority of the journey, the subspace message would continue travel through subspace on its merry way, not boosted by subspace relays.
As we know, speed = distance/time, so here comes the maths:
Fifty-one years = 446760 Hrs
ten months = 7300 Hrs
nine weeks = 1512 Hrs
sixteen days = 384 Hrs
Which, in total, is 455,956 Hours i.e. Subspace travels at a speed of approximately 2.7 million light years in 455,956 hours.
If we convert 2.7 million light years to km, we get 2.55 * 10^19 km, so that's a speed of 2.55 * 10^19 km/455,956 Hrs. Converting this into the form of X Km/Hr, we get a speed of 55,926,449,043,328.7 km/hr i.e. Data's estimation puts the speed of a subspace message at about 56 billion km/hr. For comparision, the speed of light is about 1,079,252,848.8 km/hr, so we're looking at about 56 times the speed of light
Now, how does this compare to the TNG Warp Scale? Ex Astris Scientia has a handy table for this. The result is fairly disappointing though: 56 times the speed of light would put it somewhere between Warp 3 and 4 on the TNG Warp Scale. It would actually be faster for them to personally deliver the message by travelling at Warp 4 or above!
This is, however, assuming there aren't any subspace relays. That Ex Astris table I linked to earlier also shows that the subspace relays have a huge impact upon the speed of subspace messages: it says that a subspace radio message with booster relays travels at warp 9.9999 = 199,516 times the speed of light - this would be much faster.
Now, this doesn't mean there is necessarily inconsistencies here; as pointed out in Hack-R's comment on @SS's answer, we see in Enterprise that, without subspace booster relays, it subspace messages can still be relatively slow compared to those which have the luxury of a booster relay.
Memory Alpha makes another interesting observation: that subspace messages slow down if they don't receive a boost
In 2374, however, Voyager was able to communicate almost instantaneously between the Delta and Alpha Quadrants using a system of ancient relay stations, proving that subspace communication signals slow down over time unless amplified by a relay station.
When Janeway asks Ensign Kim why the signal was not detected, Kim explains that Starfleet vessels only monitor their standard frequencies. AM signals are not within this spectrum because they only travel at the speed of light, too slow for interstellar communications.