Specific Skype Connection Lag

Hey everyone. I'm a long-time skype user and have been a premium and paying member for a very long time. I have used Skype extensively for many years and I'd say I'm an experienced user.

I have a problem that has been ongoing for a few months that is quite complicated, but I'll do my best to explain it.

Essentially, there is a particular Skype user I video call with. I've been doing this for one year, and we haven't had problems until recent months. Within the last few months (~4 months) our Skype video calls have degraded severely.

In the old days a few months ago back until when we started calling, my friend would have an upload speed of ~100-120kb/s that I would receive from them, and I would upload around ~60kb/s to them. This was wonderful. Now I've measured this using the Skype technical information window as well as a third party program called NetLimiter. Back in the day, we both had a strong clean connection to one another of greater than 50kb/s upload and download for our video chat, with 0 relays in our connection. This was before our problem started.

Now (starting around 4 months ago), around 95% of the time my upload rate to my same friend during a video call is stunted at around 2 or 3kb/s. By this, I mean they are still sending around ~100kb/s to me and I'm seeing them clearly at 640x480 video resolution, however for some reason my connection is only uploading at 2 or 3kb/s resulting in horrible audio and horrificly bad video resolution and bitrate. After some minutes it might jump to around 7 - 10kb/s upload, but it'll always fall back down to 2-3kb/s within a minute. This is what now happens 95% of the time for the past ~4 months, and I have tried a lot of things, as I have listed below:

- My normal upload speed to all other Skype users (and this particular friend before this problem started) is around 60kb/s, not this 3kb/s that I've been getting!
- My internet is not shaped or capped or anything like that. This problem has been going on for a long time so that's not a cause.
- This problem ONLY happens with the ONE PARTICULAR skype user. All other calls I have with ANY other user, this problem doesn't occur.
- I have tried using other computers. I have tried multiple windows machines, Skype for Android, and Skype for linux.
- I have turned off and even uninstalled all firewalls and antivirus software to check for interference. I have even tried this on fresh windows installations, and the problem still persists.
- I have tried using a new router, restarting routers, using wireless/wired connections.
- I have measured my connection speed multiple times, and my friend has measured theirs as well using the Skype technical information and a third party program called NetLimiter. On my end, Skype is only uploading to them at ~3kb/s and on their end Skype is only downloading at that same 3kb/s.
- My friend has tried disabling all antivirus and firewalls as well.
- I have tried using a new Skype account. In fact I've tried using lots of different Skype accounts. As soon as I log into a new Skype account and start a new call with my friend, Skype goes great at it's normal 60kb/s upload for about 30 seconds before plumetting down to ~3kb/s once again. It's ridiculous.
I've done various speed tests, (we both have), measured my connection in calls with other users, uploaded files to webservers, and all these tests show that my connection really still is ~60-70kb/s. Except with this ONE user of course.

I have monitored Skype's bandwidth usage as a process through NetLimiter as well and always see it using only 2-3kb/s in a video call. I have checked my friends network thoroughly and NOTHING else is using their bandwidth on their network or on their computer. Their connection is also significantly better than mine in both download and upload. When I look at the technical call information, sometimes we have more than 0 relays (often 4), and sometimes we only have 0. It doesn't seem to make a difference to my upload speed when it's super slow.

We tried using Google Hangouts, Ekiga, Oovoo, and other similar applications (although none are as good as Skype), but we did it to test if the problem exists on other programs. It doesn't. It's ONLY Skype doing it. I have exhausted a long list of troubleshooting ideas, and I'm at a complete loss as to what to do.

Our video calls have been completely ruined for a long time now and we're at our wits end. I've been a paying customer for a number of years now and I feel like I should turn to the community to see if there's anything else I can try. I thankyou all in advance for any light you can shed on the issue. Some details about our machines and connections are as follows:

My Machine: i7 3770k CPU, 16GB RAM, Gigabyte Z77X-D3H, GTX670, Windows 7 Ult 64bit, etc.
My Connection: ~3.3mbps down (~400kb/s down), ~0.6mbps up (~75kb/s up)

His Machine: 3 year old HP laptop, i3 CPU, 4GB RAM, Windows 7 Enterprise (I think 32bit?)
His Connection: ~33mbps down (~4mb/s down), ~2mbps up (~250kb/s up)

We both use the latest version of Skype, although we've tried using older versions too.

TL;DR: Used to have ~60kb/s upload to my friend in video calls, have only been getting 3kb/s in the past 4 months. Nothing has changed, I've tried a LOT of troubleshooting. It's ONLY the one particular Skype user, and no other video/voice chat programs do it except Skype.