Searching the Security event log is only going to be useful if logon events are being audited, which I don't believe is enabled by default. You'll need to enable auditing in the Default Domain policy in order to turn on auditing on yor non-DC servers (unless you have an OU and GPO specifically for your servers and you're blocking inheritance or setting the GPO to enforced, then you'll need to edit the applicable GPO). In addition to that, services configured to use domain accounts will be logged in that servers Security log when those services start, not the DC's Security log.
A service configured to use a domain user account will generate an Event ID 528 in the Security event log with Logon Type 5 when the service is started so you can filter the Security event log for Event ID 528 events to narrow the results.
I just verified this in my own environment (I think I did, based on my tests) so I believe this information is correct.
Another item to look at would be the Scheduled Tasks on each server and see if any of them are configured to use any of the service accounts. If so, you'll need to change the passwords on the Scheduled Tasks as well.