You didn't specify the environment (windows-service could mean managed or unmanaged). I'm going to guess you're working in native code, probably C or C++. If that's the case you need to be certain you're using structured exception handling from windows and not the C++ try/catch mechanism. Depending on your compiler vendor, the C++ implementation can't catch all exceptions.
In managed code, depending on framework version there are unhandleable exceptions. Excluding those, you also can fail to catch an exception if you don't prepare a constrained region and carefully follow the CER rules. Also as someone else mentioned, you can watch unhandled exceptions in your AppDomain. (You may not be in a single app domain but this is uncommon and you'd probably know if you weren't).
One more thing to remember in either case is that each thread has it's own stack and set of exceptions. If you're trying to try/catch all exceptions, you need to catch every thread that is working on your behalf. In managed code, the finalizer thread (garbage collector thread that executes "destructors" or finalizer code) is one place that is often missed.
However, before I jumped to either of those, I'd look for a process exit or a non-exception exit clause.