Intermittent INVALID_LOGIN from SOAP API that started on or about 2/16

Starting on 2/16 we started seeing intermittent failures from the SOAP API in our sandbox environment. The behavior seems very strange. Almost like we reach some hourly limit.

Note that we don't generally do logins until we get a token expired kind of result. Then we attempt login for a new token.

The failure looks like this - [SforceService.LoginFault]: INVALID_LOGIN: Invalid username, password, security token; or user locked out.

Of course, the credentials are not wrong and have not changed in many months.

Check this graph

This is an idle period last night. The application has background processes that continually hit Salesforce SOAP API for whatever reason. Notice each hour the last failure is at h:59:59. Everything looks good for 35 minutes and then failures start again at h:38.

We run a lot of automated testing on this environment. Check this graph.

Notice how the numbers get bigger from 1am to 7am (during the nightly regression), but the pattern is exactly the same.

One more graph.

This graph is for the last 30 days. Notice the issue started on 2/16. We never saw the issue before.

- Has anyone here seen similar behavior?

- Is there some NEW hourly max on the number of transactions?

Any ideas?

Thanks in advance.