There is a rule in compression, quality, size and speed, pick two of three. Video compression is an incredibly complex process that requires a lot of resources on either the CPU, GPU or both. You can get around that one of two ways, you can either reduce the level of compression (with lossless being the fullest extreme) or you can reduce the quality (making larger approximations means the video has more artifacts, but is simpler to compress).
Unfortunately, in the case of video games, this problem is compounded as the game itself requires the same resources that the video encoding requires. This means that your best (and really only) option for high quality, high compression encoding of video games is to move the processing off the resources that the game is using.
Most simply, this generally means using specialized real time encoding hardware that is optimized for making real time, high quality streams. Such hardware is unfortunately not particularly cheap and generally runs around $100 on the low end to over $1000 on the high end, with $200 to $500 being around the point at which it becomes "professional" hardware, depending on the features of the device. Unfortunately, this solution doesn't help your scenario at all other than suggesting that you may want to include support for some of the most popular real time encoders to be used with your game natively.
You can also try doing it by capturing uncompressed on one system and streaming that data over a really fast network connection to another computer and have that computer do the encoding. This can be a bit cheaper if you already have a second powerful computer and a fast (gigabit or higher) network, but if you have to build a computer for it, the real time encoder is a better option as it is cheaper than a dedicated PC for the job and will do a better job anyway. You might consider building your own client that could simplify this process for users.
One thing you can do is use the encoder support built in to some more recent graphics cards. Some cards have started including their own consumer level encoding support for doing things like streaming. If you tap in to this functionality, you would be able to make pretty good quality encodes on the fly.
Overall, your best bet though, is probably to capture to a lossless or near-lossless quality file and then encode it after the fact. You can include an encoder of your choice and batch things up to run during free cycles that the game isn't making use of. After compression finishes, you can get rid of the full size file.
I'd also suggest at looking at some of the codec options used by software like FRAPS to determine what might work well for that high quality, high speed codec that would make the files a bit smaller, but always keep in mind that the more compression you do, the more it will impact the performance of your game.