Cueing is generally important to DJ mixing. If I follow you correctly, your ideal setup is basically using Virtual DJ as just virtual decks: the audio is going into separate mixer channels via the Denon's two stereo outputs, and you're doing the actual cuing and mixing on the DJM3000.
What you need is some way to record the output of the mixer.
Currently, plugging that into the laptop's microphone jack isn't sounding that great. This is, in all likelihood, because the mic jack isn't designed for line level inputs, and is cheaply made to boot. It's never going to sound that great. If you're determined to record on your computer, some other kind of input will be necessary to get a decent sound. You might have a stereo line-in jack that sounds decent enough to use, or you could invest in an external interface like AJ Henderson suggested in his answer. You'll have to run some other software in parallel with Virtual DJ to handle that recording, if that's not a problem then this should work fine.
You don't have to use your computer though - anything that can record stereo line-in decently should work.
You could use a portable stereo recorder:
Really, anything at all if you like the sound of it and it accepts line-in:
(All of these images are just categorical examples found on Google Images, not specific models).
The only piece in your signal chain that should be reducing your quality that noticeably is your microphone jack. Everything else, barring defects or failures, should be plenty high-quality. You'll never completely match the fidelity of an all-digital recording within Virtual DJ (that doesn't have to go through any analog signal path at all) but the difference should be minimal and, if your equipment sounds particularly good, possibly preferable.