This legacy windows service could be started before the queueing infrastructure is up and fully operational, must fail in the initial connection and therefore isn't processing messages.
The first thing that I would check (unless the windows service has proper logging) is if there is a windows service dependency that is properly set up - you don't want your legacy service to fully start until the MSMQ service has itself completely started.
I don't think there is a problem in the legacy service per say since once you restart it, it seems to work fine, I think you have a resource-available-race type of problem where the consumer starts before the resource and it wasn't completely designed to recover from that.
I would: create a service dependency (can be done in the SCM) and then reboot the server and see if you have any more MSMQ messages pilling up, my guess the answer will be no.
Hope this helps