Very Slow Login to Domain

Over the last few months, our sites have been having issues with very slow logins (5-25 minutes.) We are running Active Directory 2008 servers with Windows 7 clients. We've tried a lot of different things so I will try to present the data as clearly as possible. Any help would be greatly appreciated!

*The slow login is not model specific. It affects both 32 bit and 64 bit desktops.
*If the computer is plugged directly into one of our Cisco switches and has this problem, it will log in slowly every time. However, if it on another mini-switch the problem will hop from computer to computer and never be consistent.
*We think we have ruled out any software conflicts or viruses on the client side through tirelessly logging of every application and cleaning these computers with every anti-virus we have available to us.
*(This is the tricky one.) When we enable verbose logging, we see that it is freezing on applying group policies, but never the same set of policies. Sometimes it gets stuck on applying computer policies and sometimes it gets stuck on applying user policies. We have tried moving these computers and accounts to the top of our GPO tree so that we can eliminate and specific GPO's that are the problem. No improvement. We have also tried applying the "always wait for the network at computer startup and logon" policy. The computers that have the slow login also take about 5 minutes to even get to the login screen when this policy is in place. To me, this means that it is having trouble authenticating to one of our domain controllers. I may be mistaken though.
* Running ipconfig /flushdns fixes the issue for a few days, but only if it plugs directly into one of our Cisco switches. If the computer is on a mini-switch, a dns flush doesn't do anything.
*When we run wireshark, it shows us that the client is communicating with our domain controller at that building. So we know that it isn't reaching out to another site's DC.

The only other solution that we have found for this problem is to reimage the machines. We have only just begun doing this so we aren't sure if it is a temporary fix or a permanent one. Like I said, any help will be greatly appreciated! Thank you for taking your time to read this.