You need to add a delay before stopping the service when it is starting. Hopefully you have most of the service functionality in another class and the ServiceBase is just a shell in which case you can have something like below.
protected override void OnStart(string[] args)
{
if(licenceIsValid)
{
_realService.Start();
}
else
{
ThreadPool.QueueUserWorkItem(delegate
{
Thread.Sleep(TimeSpan.FromSeconds(10));
Stop();
});
}
}