The Search Service is not able to connect to the machine that hosts the administration component.

I've seen many posts about people who are trying to deploy the search service and are receiving this message. Unfortunately most of the solutions I've see say "Rebuild the farm", "Delete the service and start over" or some other doom and gloom scenario. I've found something that seems to be consistently missed - PERMISSIONS

When the Search Administration Web Service for Search Service Application component is created, it is only granted access as Local Farm - Full Control. Basically if you're not creating the Search Service as the Farm Account, you will see this message.

Never fear! There is a very easy fix. Give your installation account permissions to the Search Administration Web Service for Search Service Application.

This will prevent you from having to delete the service, rebuild your farm and lose your sanity.