Are you sure it was deleted and not just closed? I've had users that closed an address book and thought it was deleted. To check just goto the address book, file >open book > and any closed books will be listed. If that isn't it, a restore is the only other option I know of.
Cheers,
Mark ;-)