Drupal 7: "Maintenance mode" message when the site is NOT in maintenance (Yes, I´ve cleared cache, 4 times now)
Search variable table in database. Variable named maintenance_mode should be there, and should be a serialized representation of false (or numerical 0). If it's not, your site will have a problem.
If this appeared after upgrade, re-running update.php might help