Before you answer I'm using a Netgear WNR2000v2 with wireless 'N' capability which has two internal antennas.

I have tried the windsurfer and parabolic dish method but not on my router because it has no EXTERNAL anntenas so I placed the dish/windsurfer on my MadCatz Xbox 360 Wireless 'N' Adapter which has one external antenna and also benefits from wireless 'N'. The connection is OK but in game (Halo:Reach) it says [Warning!].
I'm never host/lag every 1 in 3 games due to poor reception & maybe speed. This is important for gaming.

I've tried changing channels from auto to 1 to 6 to 13 and to everything between. I also ran a speed test at 17:21 today, (note that its probably peak time now).
Speed Test: From my home to server in London named Cellc. (Less than 50 miles away).

Result:
Download - 1.54 Mb/s (1540 Kb/s) (Download speed means data from them to me)
Upload - 0.46 Mb/s (460 Kb/s) (Upload speed means data from me to them)
Ping (Response time) - 94 milliseconds
ISP: Virgin Media (up to 100mbps, cable modem to router connection).

Note that I cannot relocate my router or wireless adapter because they are a room apart.
I won't use powerlines because I don't have a job so I'm not wasting money on that.