Hi there, sorry for the late response. I hope you will be fine now with Domino. But for the record our problem and solution: Same problem, Windows 2008 64 bit, Domino 8.5.1, service does not start. Can only run as application, but this was not an option.
After a long discussion with IBM (John Paganetti; thanks John!) we found that there could be a conflict with the controller IP port.
I added one line to the server's notes.ini:
If IP address of Domino Server is: 18.104.22.168
In notes.ini, below Ports=TCPIP
you would add