@riseN- do you mind sharing a VOD from your test stream? You don't have to, but I'm curious to see what it looks like, if we have the same perception of compression artifacts :)
I say that because 720p30 at 3000-3500 kbps should be pretty good.
Other than that, if you take a game at 1024x768 and stretch it out to 1920x1080 it's not going to be super crisp and sharp. You would get a better picture by playing the game also in 1920x1080. But I understand that a lot of people want to play like we did in the 90's ;)
As mentioned by EBrito here you could alter your base resolution. I suggest setting it to 1280x720 and output to the same. You will have to type in the base resolution manually for that, it won't be in the drop-down list.