Drupal 7: "Maintenance mode" message when the site is NOT in maintenance (Yes, I´ve cleared cache, 4 times now) I get the "Operating in maintenance mode. Go online." message and the D7 site is not in maintenance mode.

The message doesn´t appears all the time, and sometimes it goes away when I refresh the page.

I´ve cleared cache. I´ve tested and it is most certainly NOT in maintenance mode.

I´ve checked Drupal Error reports, and I get this one (I don´t know it it´s related or not with the problem):

TIPO    acceso denegado
FECHA   Martes, 14 May, 2013 - 01:11
USUARIO Anónimo (-)
UBICACIÓN   http://www.liga.net/cron.php
REFERENTE   
MENSAJE frontpage
SEVERIDAD   advertencia
NOMBRE DE LA MÁQUINA    xx.xxx.xx.xxx
OPERACIONES 


Sometimes in a complete random way, as an anon, it appears the page "site offline". When I reload the page it´s up again...

Any thoughts on this will be very much appreciated. Thanks!
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