I read in some of your earlier posts, Kasumi, that sprite palettes can be switched out every scan line. Are there any original examples where this technique was employed?
First I will say we are definitely getting into things that may be inconsequential to know unless you are really making an NES game, but I will answer your questions regardless:
Sprite palettes every scanline? Nothing comes to mind. Changing the background palettes takes exactly the same timing, though. I linked a video of this in my last post:
http://www.youtube.com/watch?v=ecJiKqQonDc It's not done for a reason. Say I'm changing the sprite palettes every scanline. (Which... is mostly impossible to do while actually displaying sprites. Updating palettes can only be done during vblank. Updating sprites for display can only be done during vblank. Doing this the easy way takes almost a quarter of the vblank time, and updating the palettes every scanline probably takes almost all of it). But let's say for a second that it's possible. Let's say I have four identical boxes that are all using palette 0 arranged like this:

They're allowed to be different colors using the same palette because that palette is being changed every scanline. But... what happens when one of the boxes in the middle moves two pixels up, and the other moves two pixels down? Probably something like this:

I'm sure there are games that change the sprite palette
once mid rendering, but none immediately come to mind. What Kirby's Adventure and Super Mario Bros. 3 do to get their HUDs not to move with the background is nearly exactly the same, except they write a byte to change the scroll rather than bytes to change the palette. Changing the background palettes mid frame can be used for many more practical things, but it's the same difficulty to change either the sprites or the background palettes.
In SMB, there are a few sprites that change palettes within the same level (red/1up mushroom, red/green turtle, etc.) How does palette swapping work in that case?
There are 64 hardware sprites. They're not always visible, but they're drawn every frame. Each sprite has 4 bytes that tell it how to be drawn. There are 256 8x8 tiles that can be used for sprites that the NES has access to at any given time. Newer cart hardware allowed them to be changed, but Super Mario Bros. never changes them. Here are its sprite tiles:

Every moving thing in that entire game uses only these.
Now, one of the four bytes given to each hardware sprite tell it which of the tiles to use. If I write $00 to it, the upper left of Big Mario's head gets displayed using that sprite. $01, the upper right part of Big Mario's head. If I write $A0, I get a part of a koopa's head.
Another of the four bytes has two bits that tell the hardware sprite which palette to display as. Two bits, two possibilities per bit. 4 palettes. The rest of that byte is used for sprite flipping, and whether or not the sprite is drawn behind the background.
The other two bytes are for its position on screen, one for X and one for Y.
So Mario has a red koopa on screen. It writes $A8 to one hardware sprite's tile byte. It writes the other tile numbers to the other hardware sprites that would make up the koopa. It writes 2 to the palette bits of all the hardware sprites that would make up the koopa. The koopa is draw using those tiles, and red. To change its color to green one would just write 1 to those palette bits instead of 2. If I wanted to add a green koopa to the screen at the same time, I'd go to the next set of hardware sprites and do exactly that. Write the same tile numbers to the new hardware sprites, but with 1 for the new palette bits instead of 2. The sprite palette NEVER changes in the middle of a Super Mario Bros. level. (IIRC) How about when Mario gets a star? Setting all his hardware sprites to a different one of the four palettes quickly is all that's happening to make him flash. Super easy. He actually flashes different colors when he's underground than when he's above ground because the palettes are different, but the game logic is not. flashing ? Mark blocks is done by updating the actual background palette.
Displaying and moving sprites on NES is one of the easiest things you can do with it. If I want a hardware sprite to move, I write a new byte to that sprite's X location. It'll be there next frame. I want to change its tile, I just write the tile I want to a byte in RAM. All the rendering is done automatically. Because the order the NES draws the hardware sprites in is always the same, you have to make sure to use higher priority hardware sprites for overlays, but... inconsequential. Too much information?

The different behavior between the different koopas is just game logic, if that's what you mean. Both the program and the NES don't care what the koopas eventually end up looking like. I could hack Tetris to turn off the rendering, and still play by looking at where the blocks are in RAM.
Meanwhile, I'm trying to come up with a fourth palette that would utilize pink, so that I don't waste a whole palette on overlay colors.
A good idea, but I wouldn't worry about it if you have trouble. There's nothing stopping you from using the mouse's colors to overlay on top of what I've been calling the overlay palette. Any single (not hardware) "sprite" can technically use all 12 sprite colors.
Anyway, I often worry making posts like this scares others away, so if anyone has critique for the aesthetics for him please post!Here are some quick points of mine. The cat looks as though he's holding his head back in surprise. You could shift his head a pixel or so to the left. I also wonder why he's in a different perspective than the others. I'm also not sure if the change the Mr. Cuddles was successful. At 1x, I'm not sure I can't quite tell it's a tongue, and at any other zoom, I see only an eye in his mouth. I like the new feet on the mouse much more.