How to apply css to the maintenance page?
Override the maintainence stylesheet in the theme layers .info file...

  stylesheets[all][] = system.maintenance.css


To be honest if none of your theme stylesheets are loading then not sure it will work but ideally it should.

Heres some more info on theming the maintence page...

http://drupal.org/node/195435



UPDATE

Alternatively, try the following in your theme...

/**
 * Implements hook_preprocess_maintenance_page().
 */
function YOURTHEME_preprocess_maintenance_page(&amp;$variables) {
  drupal_add_css(drupal_get_path('theme', 'YOUR_THEME') . '/css/maintenance-page.css');
}