Up until now, I've been treating the VideoNuLA extended attribute text mode as though it supports one background colour and 8 foreground colours. VideoNuLA is actually more capable than that; we can have 8 pairs of (foreground, background) colours, and any character can use any one of those 8 colour pairs. So we can have, say:
- Pair 0 - white on black
- Pair 1 - red on yellow
- Pair 2 - yellow on black
- Pair 3 - magenta on red
- Pair 4 - magenta on blue
- Pair 5 - black on magenta
- Pair 6 - yellow on blue
- Pair 7 - cyan on magenta
The basic ANSI colour codes allow the running program to choose from the foreground and background independently from the 8 primary colours, so there are 64 pairs possible and the 8 pairs we have available aren't sufficient to handle this.
What I've tried to implement is a scheme where we dynamically change our 8 colour pairs to match what the running program has requested. So we start off with a blank screen and the default foreground of white and background of black. The program prints an 'A' character. STEM says to itself "I need a colour pair for 'white on black' - OK, let me redefine pair 0 as that, and use colour pair 0 to print this A".
The program then selects red foreground and yellow background and prints a 'B'. STEM says "OK, this is different. I need a colour pair for 'red on yellow'. Pair 0 is in use, let me redefine pair 1 as red-on-yellow, and use colour pair 1 to print this B.
We remember the pairs we've already allocated, so if the program then switches back to white-on-black text and prints a "C", we will use pair 0 for it rather than redefining pair 2 to be white-on-black. 
Everything's peachy until the program uses its ninth unique colour pair - let's say this is white-on-blue. At that point, STEM needs to allocate one of the 8 pairs to it, and they're all used. So it has no choice but to re-use one pair as white-on-blue - it will choose pair 0 (the oldest pair), causing the white-on-black text printed earlier using pair 0 to suddenly turn white-on-blue. We re-use the oldest pair as in an ideal world, all the text written using it has already disappeared fro the screen and the redefinitions isn't noticeable, but this isn't guaranteed, of course. We are also hoping that the program is showing some restraint in its use of foreground/background colour combinations and doesn't need more than 8 different unique pairs on the screen simultaneously. (I could imagine this being the case if using Elminster's telnet to connect to a Linux machine and doing things like ls --color, for example.)
I've attached a copy of the prototype and there's a new test program T.VNULA2 which prints text in random combinations of foreground and background colours, pausing for you to press RETURN after each one. Ignoring lucky cases where the same colour pair occurs multiple times in relatively close succession, you can see that after the first eight lines, colours get redefined and so the older lines suddenly appear using different colours. Here's a screenshot of a sample run (courtesy of Kieran's b-em VideoNuLA emulation): You can see that the last eight lines (16-23) appear in the correct colours, whereas the previous lines don't match their own descriptions (e.g. line 0 says it's white on black, but it's actually red on white; it was white on black when it was first displayed).
A side issue here is that this prototype doesn't do anything to avoid the not-yet-written-to character cells on the screen (which are using colour pair 0) from changing when colour pair 0 gets redefined. I can think of various possibilities here (perhaps colour pair 0 is permanently reserved for white-on-black), but I think this is less important than deciding if this basic approach is desirable.
Because the extended attribute mode always displays the rightmost column of each character cell using the background colour of cell 0, changing the background colour doesn't give a contiguous horizontal background colour - you can see in the screenshot that there's a white vertical line between each character cell on every line. This can't be avoided (although the colour of that line doesn't have to be white; that's just how it happens to be in the example) in the 8 colour mode; the 4 colour mode wouldn't suffer from this (but STEM doesn't currently support setting background colours at all in 4 colour mode). [Edited to add: does a real VideoNuLA behave like this, or is this an emulation bug? I have no reason to believe it's a bug but I thought I'd ask. I could see this alternatively using the background colour of the pair for the character cell itself rather than the background colour for colour pair 0.]
Note that if the program running under STEM doesn't use any background colour codes, this approach is more-or-less equivalent to how STEM behaved before, as the 8 colour pairs we have are always enough without any redefinition being needed. (However, foreground colour 0 was previously treated as red, whereas it's now black and therefore is not very useful if you aren't changing the background colour.)
 There is a flaw in the implementation of this in the prototype, as I don't have a proper least-recently-used list, but it does more or less work. The effect of this is that sometimes a colour pair which was used quite recently will be redefined earlier than it should be.