A lot of airspace is not covered with primary radar, at least not for ATC purposes.
Most airspace above seas and oceans are not covered by ATC primary radars. ATC relies mainly on secondary radar for surveillance, primary radar is used mainly for airspace infringement protection and airport surface surveillance. Over oceans and remote areas procedural control is used, without any surveillance.
Most primary radars used for long range surveillance in ATC are operating in the L-Band. L-Band signals do not follow the curvature of the earth very well; at low altitude the range is limited because the aircraft are below the horizon. At higher altitudes the range is up to about 250NM, but only when the radar is operated at very high power, which is costly both in design and electricity bill. In many cases it is not needed to operate at long range.
Radar is also shielded by terrain; in mountainous areas it is difficult to cover the valleys. In Europe, and I believe also in the US, high altitudes are well covered by primary radar, at low altitude there are many gaps.
A lower band (HF - UHF) radar can be used to look over the horizon (OTH radar). This type of radars is used for Air Defence purposes. The resolution is very poor compared to radars used for ATC but it serves well as an early warning system for incoming enemy aircraft and missiles. This type of radar requires huge antenna arrays, over a kilometre long and they consume enormous amounts of power.
The effective range is typically about 3000 km. For example Australia has the Jindalee Operation Radar Network, that can see past Jakarta, Indonesia.
In case of the missing Malaysian MH370, and the latest suspicions that the aircraft ended up West of Perth, I wonder whether the flight was tracked by the OTH Air Defence radars of Australia.