How is it that when I play a game in fullscreen (either for the effect or when I want to record a video), sometimes parts of the screen becomes black until something is animated on the black zone. This is especially annoying during cutscenes where cursors are deactivated (so it can't be cleared easily).
I would like an answer soon. I'd like to record a Shadow of the Comet walkthrough (to match my Alone in the dark walkthroughs) with FRAPS (hence the fullscreen).

Maybe use dosbox its own recording feature ?
I didn't experience missing screen updates in fullscreen though

The glitch happens when I play, whether I record or not.
I stopped using Dosbox recording feature. It worked well with Alone in the Dark as I could still resynch my videos with VirtualDub by processing every 2 frames, but it didn't worked anymore when I tried it with Bioforge (the video remain un-synched no matter what I do. Lack of CPU processing power?) which is why I switched to FRAPS.
It also happened with Stonekeep (although not has often). I wonder if it's due to the graphic mode used in fullscreen (and it happens ONLY in fullscreen).

You probably have . . . but make sure you are running the latest version of DosBox http://www.dosbox.com/
DOSBox 0.73 has been released!
Most noticeable changes:
* Support for more graphics modes and cards.
* Improved Vista support.
* New OPL emulation cores.
* Sound fixes and improvements for Mac OS X.
* Lots of compatibility fixes.
* Lots of cdrom detection improvements.
* Lots of memory (EMS/XMS) improvements.
* Various fixes and enhancements for the recompiling core.
* Support for evdev.
* Lots of DOS fixes.
* Slightly faster!
* More stable.

Was the reinstall from the original system disks/ system restore you got with the computer? If so, did you do all the updates from Windows update and install the latest video driver?
Are you running Vista? If so, right click the game shortcut, click Properties, Compatibility and check mark Run this program as an administrator. Maybe do it for DOSBox as well.

This might be helpful as well, this config file is for the CD version so you might have to alter or change for the version you are running, good luck!
More info on dosbox conf at http://www.dosbox.com/wiki/Dosbox.conf
To test, change drive letters to your own and copy / paste the text below into a file named . . .dosboxShadowComet.conf
[cpu]
cycles=3000
core=normal
cycleup=500
cycledown=20
[dosbox]
machine=vga
memsize=16
language=
captures=.
[sdl]
output=surface
fullscreen=false
fulldouble=false
fullresolution=original
windowresolution=original
autolock=false
sensitivity=100
waitonerror=true
usecancodes=true
priority=higher,normal
mapperfile=mapper.txt
[render]
scaler=supereagle
frameskip=0
aspect=false
[sblaster]
sbtype=sb16
sbbase=220
irq=7
dma=1
hdma=5
mixer=true
oplmode=auto
oplrate=22050
[gus]
gus=true
gusrate=22050
gusbase=240
irq1=5
irq2=5
dma1=1
dma2=1
ultradir=C:\ULTRASND
[midi]
mpu401=intelligent
device=default
config=
[speaker]
pcspeaker=true
pcrate=22050
tandyrate=22050
disney=true
[dos]
xms=true
ems=true
umb=true
[mixer]
nosound=false
rate=22050
blocksize=2048
prebuffer=10
[bios]
joysticktype=none
[autoexec]
mount C .\data -ioctl -label shd
mount D .\game -ioctl -label shadowcd
D: SHADOW.EXE

Running DOSBox as an administrator is unnecessary; it works just fine with UAC redirection.

sounds like an identical issue that fallout 1 had with certain graphics cards, don't recall off the top of my head which ones though, might be worth a shot to try to look up if there's a resolution for that one that might pertain to you as well

The DOSBox ver 0.73 has support for more graphics modes and cards. POLE7645 says he is running that version so it didn't address the graphics card problem evidently.

Another bug that I have (on my desktop) is that every time I play on fullscreen (even with GOG games), the picture is always moved a bit to the left (so I'm missing a portion of the left side of my screen and there's a black band on the right side of my screen).

Might not be the actual problem or fix for that but I would resize and re-center the screen using my monitor adjustments. Try it and if it fixes the game screen and doesn't affect your desktop, leave it.

That's usually dependent on whatever resolution (and maybe update rate) the screen receives, and can be set using the screen's controls.
If it's a LCD, there's usually an "auto" button somewhere that you can use to let the screen adjust itself for that resolution (others won't be affected). That button only works for VGA, not DVI, but if you were using DVI the problem wouldn't have appeared anyway.
If you can't find any "auto" button (if it's a CRT or one of the rare LCD's that doesn't have it), you'll have to work your way through the screen's setting yourself (since they all differ) to shift the image a bit to the right (same thing here, other resolutions won't be affected unless the screen is over 10 years old).