To display your maintenance page in your chosen theme and not the Drupal minelli/garland style, you'll need to create a copy of your page.tpl.php file.
Save the copy as "maintenance-page.tpl.php" in your theme folder and rip out all the bits you don't need.
Now set the 'maintenance_theme' variable using variable_set() to whatever theme you wish. It should apply immediately.
Tested on Drupal 6.