Sleep mode - what can be done with Arduino?

  1. If I am using millis() and I RESET the processor, the reference counter is reseted also. If the processor enters into sleep mode for 1minute and wakes up, what occurs with the millis() reference?

Depends on the sleep mode. Most modes stop the processor's clock which stops all timer / counters including the one used for millis.

Is it reseted?

No. If the processor's clock is stopped, millis is frozen until the processor wakes. If the processor's clock is not stopped, millis continues counting.

  1. Is there "an internal" clock/timer that can be used for sleeping purposes?

The watchdog timer can be enabled to run independently from the processor's clock. But the watchdog is very inaccurate.

More specifically, a timer that we can program a certain value for timeout and continues working in sleep mode (eventually waking up the processor)?

In Idle mode, the clocks run. In all other modes they do not run except the watchdog timer.

  1. Assuming that answer (3) is negative, what kind of "feasible" solution (simple to develop and/or cheap to purchase) exists to realize the above scenario?

Real time clock. Watchdog timer. Or, external crystal driving a timer...
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1273507808