On paper reducing the fps by a correct divider should work and for some media it does. But often no matter what I try it results in jerky playback via flash.
There's been media where I've recalculated the fps several times and still had bad results using several different encoders. I finally came to the conclusion its just not worth the time to re-encode.
It could have to do with the current h.264 implementation in flash but honestly I have no clue and never really looked into it. Most of the media I work with see's little reduction in file size, its just not enough to make me want to spend time figured out if it's going to work or not.
And I very very rarely have this issue with vp6 flv. And when I do its usually because the source was botched from the get go.
As for the server speeds, might be bad routing from his server to you. This is just a cable connection. Albeit a fast one ;)
http://static.vizmu.com/images/2.3mb.jpg
Edit:
I just ran a wget 'server to server' his box capped at 10-12MB/s