1. Use ArcGIS Server built-in users instead of the Windows Domain Logins.
2. Add the secured service as an item in ArcGIS Onine and store the credentials in the ArcGIS Online proxy. All the requests go through the ArcGIS Online proxy.
3. Use the 'username@domain' format.