Lemme start by saying -- If you are doing a restoration - only the System Attendant should be started. Chances are if you are doing a full restore - you are restoring the DS too - and the Service should be stopped.
If there were any changes to the directory store before the back ups were made - those changes will be written in the logs - and the logs will have to update the directory store.
You can indeed restore an exchange server without the logfiles -- but know this - there WILL be data loss: in the form of .. missing attachments, email, and potentially missing objects in the Directory store if any were created after your last full backup.
It is possible, but not always stable. The only time you will get a stable full recovery without Transaction logs, as far as I know - and in my experience, is if you to a full offline backup. Meaning, if you stop all services and backup your PRIV.edb and PUB.edb -- then restore them just like that ... you will not need logs to replay.. because the process of shutting down the services commits all transactions to the database; so your DB's are all up to date by the time they are shutdown. That's why it is always good to have a maintenance window to do at least one Full Offline backup every couple of months.
There are times you will get a 'log not found' error after a restoration, when services try to stop and then fail, then you try to start them again... reason for this is during the replay of the transaction logs, Exchange adds a registry keep, tracking the logs read. Without deleting this key - the exchange will alway spit out a bad log error ...
I have outlined some troubleshooting steps in my faq.. if help - give it a vote....: faq10-2775
To get more info: What kind of back ups are you using, Offline or Online backups? and do you use incrementals over the course of the week?
Hope I was helpful. Alshrim
System Administrator
MCSE, MCP+Internet