What's the energy density of liquid nitrogen?
Just skimmed over the links:

Highview: 


  Using ambient heat to warm it, the process recovers around 50 per cent of the electricity that is fed in, says Highview's chief executive Gareth Brett. The efficiency rises to around 70 per cent if you harness waste heat from a nearby industrial or power plant to heat the cryogen to a higher than ambient temperature, which increases the turbine's force, he says.
  
  Batteries under development .. have efficiencies of around 80 to 90 per cent, but cost around \$4000 per kilowatt of generating capacity. Cryogenic storage would cost just \$1000 per kilowatt because it requires fewer expensive materials, claims Brett.


Here's some evidence that people who know about gas and liquid air are interested in the technology: strategic partnership between Messer and Highview

Actually Highview has a presentation on their web-site that contains a lot of information. Note that they propose to run a 4-stage process against heat (ca. 100 °C), not ambient temp.

Here are some values for energy storage efficiency comparison found after a very quick search:
Batteries (Wiki)
German Wikipedia has lower efficiency values
Energy conversion table (Wikipedia)

Pump-stored hydroelectricity: 70/75 - 80% (Wiki + de.Wiki)
(Note the difference between technology that is actually in use, so efficiencies that are achieved in practical use are known and prototypes/scientific studies about achievable efficiency.)

Dearman claims 70% efficiency for the engine. 


Unfortunately they don't say % of what (remember the low-temp heater manufacturers claiming > 100% efficiency because they used achievable efficiency with high temp exhaust gas as their denominator?).  
Neither do they say something about the power at which they have this efficiency (ideal thermodynamic efficiency is at P $\rightarrow$ 0 ($t_{cycle} \rightarrow \infty$))
Neither can we assume that they start their calculation taking into account the efficiency of producing liquid nitrogen. 
Nor storage loss.


=> so far, Highview's stationary plant concept looks more sound.



Let's have a look what thermodynamics says:  


ideal efficiency
boiling T of liquid air: 77 K
ambient T: assume 290 K => $\eta_{ideal} = 1 - \frac{77}{290}$ = 73% 
waste heat: assume 370 K => $\eta_{ideal} = 1 - \frac{77}{370}$ = 79% 
(in other words, Dearman claims close-to-ideal efficiency)
energy density of liquid $\ce{N2}$: 620 kJ/l = 712 kJ/kg (from presentation at Highview)
The Linde process is said to need approx. 500 kWh / t = 1750 kJ/kg of air
(that would be ≈40% efficiency; no real source, just something someone answered in a German-language chemistry forum)
Here's short report that gives ≈20% efficiency for producing liquid air in Egypt. They also give storage loss (ca. 0.17 \%/d)


Thus, the 50% (achieved by Highview) to 70/80% (short term goal Highview against waste heat, quote for Dearman's engine) mean that


either the liquefaction was not part of the efficiency calculation,
or they have a super efficient air liquefaction that is about 2 - 4 times as efficient as the two numbers I found.
(Anyone around here who knows? Linde, Messer, AL?)


Update: just had a closer look at the Highview presentation. Their 50 - 80% are cycle efficiency based on "Available enthalpy for cold cycle ~300kJ/kg", so less than half of the energy density they give. Calculating with 1750 kJ/kg to produce the kg liquid air, we're at 17% (close to the "Egyptian" 20% efficiency for producing liquid air), of which they recover 0.5 - 0.8.

Conclusion: electric -> liquid air -> electric cycle with an overall efficiency in the order of magnitude of 10%