[Piwoslaw]

Grille block, insulated engine bay, insulated oil pan - I assume you've tried all of these?

There are also diesels (VW and Peugeot/Citroen, for example) which have a 12V coolant heater made out of 1-4 glowplugs. Yes, these add an electrical load, but the extra load on the engine helps it heat up faster. Increases fuel consumption, but in the long run may turn out to be cheaper than a stand alone engine heater - depends on the fuel you will use.

Another option is the gen II Prius thermos - will keep coolant warm overnight, so even if you do not get full warm up now, then you have a head start next time. Check out Heat storage system (Prius-like insulated coolant reservoir).