A service account running with the credentials of a domain account that has recently changed the account password will run into a problem only during a restart of that service. Since the server hasn't been updated with the new password your service will not be able to authenticate the service account credentials until you update the service properties with the correct password.
That being said, it is recommended that you use the SERVER\NETWORK SERVICE account for services that require domain level access. The NETWORK SERVICE account is actually an alias account linking to the DOMAIN\SERVERNAME directory object in Active Directory.
ex. ServerA\NETWORK SERVICE --> DOMAIN\ServerA
Imagine your server running the service is ServerA and the resource your service needs access to is ServerB. By configuring the service to use the ServerA\NETWORK SERVICE account will actually be running with the DOMAIN\ServerA account. This has an added benefit of the automated computer password change mechanism that takes place (by default) every 30 days, transparent to you or your service.
Also, if you need to grant permissions for your service to communicate to the resource server (ServerB) in the same forest you can simply edit the access permissions on the ServerB to grant access permissions to the DOMAIN\ServerA account (remember it is the actual account for the ServerA\NETWORK SERVICE account) and then all requests to the resource on ServerB will be performed using the credentials of the DOMAIN\ServerA account.
All that being said, the Managed Service Accounts in Windows 2008 (thanks for pointing that out Oskar) looks to be an even better way to handle service account needs!