On Atari ST, it was possible to change the palette colors in midflight, and using that trick to display more colors on screen. The technique was used by Spectrum 512 and Quantum Paint and many demos.
You could also go beyond that by changing the image 50/60 times a second, which would then blur together. Enabling you to display colours that aren't even in the ST's palette.
I'm not aware of the specifics anymore but by using well-placed NOPs when drawing a scanline you could make the borders disappear on the Atari ST thus getting a higher resolution. This was one of the many advantages the Amiga had over the Atari ST: being able to use the whole screen while the ST had a screen like a letterboxed movie except on all four sides of the screen.
Toggling the register to change between 50/60Hz mode at the right time, specifically, could reset the counter in the ST's Video Shifter and trick it to carry on drawing screen when it should have been outputting blank border. Top and bottom borders were however much easier, because you could open them with just one carefully-timed interrupt each (I used Timer-B, which was linked to horizontal blank and counted lines, if I remember!). Described as far back as the B.I.G. Demo (check the scrolltext).
Opening the left and right borders however required doing it for each line, I recall, which uses a lot more CPU time. (Unless, of course, there's a trick I don't know!)
Spectrum 512 uses NOP timings to swap the palette at regular intervals throughout the screen; the "4096 colour interlaced" mode just flickered between one colour and another on alternate blanks to give the visual impression of flickery intermediates (before the STe came out, which used the high bit of each nybble to actually have 4-bit-per-channel palettes of 16). That technique, in turn, came from the C64 scene, as did the border trick, though I think they wrote the screen address?
What's old is new again: plenty of lower-end TN LCD panels pull the same colour trickery to fake 8-bit colour from 6-/7- bit panels (or, reportedly, 10-bit deep colour from 8-bit ones in some cases).
This demo is crazy. I don't think CGA even gives them a VBL to hang off! Wonderful.
You're close with respect to the C64 border trick.
On the C64, you could pull the border in the width / height of one character in order to support smooth scrolling (coupled with registers to set a 0-7 pixel start offset for the character matrix). This was done so that the borders wouldn't move in/out while scrolling.
By turning this option on/off precisely timed, the VIC graphics chip never found itself at the "correct" location to enable the borders, and so never did.
Opening the top/bottom borders was done very early because it didn't require much timing.
Opening the left/right borders with static sprites happened soon afterwards.
Opening the left/right borders with moving sprites was particularly nasty because the VIC "stole" extra bus cycles from the CPU for each sprite present on a given scan line, so if you wanted to move sprites in the Y position and open the borders, you needed to adjust your timing by the correct number of cycles for each scan line, often done by jumping into a sequence of NOP's. There were additional complications, but that's the basics.
I think DYSP (Different Y Sprite Positions) on C64 was first achieved in 1988.
What's old is new again: plenty of lower-end TN LCD panels pull the same colour trickery to fake 8-bit colour from 6-/7- bit panels (or, reportedly, 10-bit deep colour from 8-bit ones in some cases).
That's known as temporal dithering/FRC (http://en.wikipedia.org/wiki/Frame_Rate_Control ). To get the 2 more bits of "fake" colour depth requires a 4-frame cycle, on which you display either the darker or lighter colour in sequences like 0000, 1100, 1110, and 1111. It's a form of PWM and the same technique used to drive those large outdoor graphic LED display signs, although to avoid flickering the frequencies are in the tens of kHz.
Vague details from memory: To make the vertical borders disappear, you could reset the refresh timing (maybe it was just by switching from 50Hz to 60Hz mode) halfway through a frame, and the video chip on the ST would desync from the retrace in the CRT. The only way I know to draw on the horizontal borders of a vanilla ST was by perfectly timed border color changes - I used that along with the compiled sprites technique discussed elsewhere in this post, to write a border-less horizontal scroller.
"QPs 512 mode is pretty straightforward; its only color limitation being that it can display a maximum of 40 colors on a single scan line. Mode 4K uses a special technique called "interlacing" in order to display a supposed 4,096 "colors -- http://www.atarimagazines.com/startv3n2/quantumpaint.html see also http://www.atari-wiki.com/index.php/ST_Picture_Formats