The images below shows some of the tricks used in the C64 game Creatures to achieve the illusion of more colors. The games uses a horizontal scrolling playfield in multicolor character mode. The main trick used is to have the shared colors be light and dark midtones, while using the unique tile color to either add a shadow or a highlight to the tile. When you look closely, you'll see that a highlight and a shadow never occur on the same tile.
Another interesting game is Stormlord, with that one there is however the catch that I have absolutely no idea how it managed to do so many colors. It is again a horizontal scrolling title, but unlike Creatures it doesn't seem to use any obvious scanline palette switches, instead it actually uses more then four colors on a single scanline, like in multicolor bitmap mode, but that normally doesn't go together with scrolling. My current assumption would be a multicolor bitmap mode with custom blitting code and VIC bank switching to a second buffer, so that screen redraws can happen in the background and the buffer get flipped each eight pixels when the scroll-offset reaches its edge:
PS: All this analysis was done by looking at a screenshot, not by actually observing the C64's memory, so there will be bugs.