SQL Server and SSPI handshake failed error
Why does a reboot of the server sometimes fix this issue?

I think the OS has an issue talking with the DC (for whatever reason(s) you determine) and when this happens, it just gets out of sync somehow with DC, AD, etc. and a quick fix is to reboot the SQL Server OS when this occurs and there is no network communication with the DC at the time of the reboot, and all comes up fine with everything back in sync at that point. To accurately answer this, you probably need to find the reason first. 



Proving that [the] Domain Controller(s) is/are or is/are not the issue

1. Troubleshoot &amp; Consider



  I'm not suggesting you make a bunch of changes before trying to find
  and fix the specific problem beforehand but there are many factors to
  consider I would think. It's just something you have to troubleshoot
  one step at a time unless there's something obvious causing the issue.



2. Access Perspective



  In my setup, I'm the domain admin as well as the DBA so I have access
  to everything and all servers (two domains with two-way trusts) to
  troubleshoot at all levels whereas you may be a bit more restricted
  with what you can review, etc. on each server in the loop of the
  issue.



3. No Simple Oversight



  I usually start with the simple items first that don't require changes
  and see if there are any obvious issues (e.g. event viewers on all
  servers, DNS testing on all servers, review all server configurations,
  etc.).



4. No Telling Logic



  This could be an issue at the OS level of the SQL Server for the
  Windows version it is on. This could also be an issue with the NIC of
  the SQL Server or a mis-configuration of TCP/IP or DNS settings on the
  SQL Server or any of your DCs.



5. Collect &amp; Update



  Gather information on or ensure the SQL Server is fully updated with
  Windows Updates, and ensure server firmware is up-to-date if
  applicable with BIOS version as well as any hardware device firmware
  updates. The domain admins could also do the same on the DCs but use
  caution with making a bunch of changes and do so one step at a time.



6. Best Practices



  I'm not sure how your AD and DCs are configured topology wise, but
  best practices should be followed as best as possible and a DC should
  be close to the network where both domains are physically rather than
  going across a slower network pipe or routers, etc. which adds another
  level where there could be issues or configurations to review.
  
  The DCs should have their TCP/IP settings configured so that their DNS
  settings point to other DNS servers or follow best practices otherwise
  as per Microsoft for the DCs configurations applicable in your
  environment.



7. Request Access or Configuration Disclosure Assistance



  You'll need to do basic troubleshooting to find the issues to resolve,
  ask questions, see what all could be updated and patched or changed,
  and get your domain admins to help you troubleshoot or disclose domain
  configurations to you if you're not sure how to see if everything is
  configured as best it could be for optimum performance and per best
  practices.



Important: This not to say there couldn't be a very simple reason this suddenly happened but if nothing has changed anywhere (i.e. OS on DCs or SQL Server, network configurations, AD or forest functional levels, hardware upgrades, Windows Updates, etc.) then you just have to troubleshoot for the reason why one step at a time.