When stopping and starting Exchange server 5.5, you want to stop the services in the following order:

IMS (Internet Mail Service)
MTA (Mail Transfer Agent)
IS (Information Store)
DS (Directory Service)
SA (System Attendant)

To restart all the services needed, simply restart the IMS.

However, when troubleshooting, sometimes it's a good idea to start them one at a time, and read the logs in between. Eventually, one will fail, and it will be more clear which one's causing Exchange not to start.

So, the proper order to start them would be:

SA (System Attendant)
DS (Directory Service)
IS (Information Store)
MTA (Mail Transfer Agent)
IMS (Internet Mail Service)

Also, if you start them from the command-line, you'll see immediately if a service doesn't start.

To start services from the command-line, use the following syntax:

C:\> NET START "long-service-name"

The "long service name" is what the service is called in Service Manager, and you enclose it in quotes.