I suspect there are two problems. The occasional random lockup is probably due to the use of the String data type. Over time, this can fragment memory and fail. You should switch to using normal C strings (null-terminate arrays of characters).
Not resetting when cycling power is something else. I would agree with DrAzzy that the board must be getting power from somewhere (and yes, it could even be supplied through one of the IO pins).