Hu. That seems very promising indeed. Good work!
Not sure on whether green is already taken, but why not use the full range from green to red for the name?
Come to think about it, with this one could remove the hard distinction between spy level 1 and 2 somewhat, and have the suspicion simply rise slower for an expert spy.

I'm currently fitting your above code into the trunk, and have come upon a serious bug in GuySawEnemy(...):

// consider guys in this team, which isn't on our side
for ( ubIDLoop = gTacticalStatus.Team[ ubTeamLoop ].bFirstID; ubIDLoop <= gTacticalStatus.Team[ ubTeamLoop ].bLastID; ubIDLoop++ )
{
	pOpponent = MercSlots[ ubIDLoop ];

MercSlots is an array of SOLDIERTYPE* where we add any soldier, one after another. We're even mixing teams in there it seems.
MercPtrs is an array of SOLDIERTYPE* where soldiers are in specific sections of the array (first 32 is mercs, then 6 slots for vehicles, then 64 slots for the enemy and so on).
As a result, using gTacticalStatus.Team[ ubTeamLoop ].bFirstID and gTacticalStatus.Team[ ubTeamLoop ].bLastID only properly works on MercPtrs, not on MercSlots (we loop over that via guiNumMercSlots). This causes this function to not work as intended.

Edit: I'm not really a fan of the 'uncover spy automatically when in combat and we've seen any hostile', so I'm skipping that part.

BOOLEAN GuySawEnemy( SOLDIERTYPE * pSoldier, UINT8 ubMax )
{
	UINT8		uiLoop;
	SOLDIERTYPE *pOpponent;

	for (uiLoop = 0; uiLoop < guiNumMercSlots; uiLoop++)
	{
		pOpponent = MercSlots[ uiLoop ];

		// if this merc is inactive, at base, on assignment, or dead
		if (!pOpponent || !pOpponent->bActive || !pOpponent->bInSector)
		{
			continue;
		}

		// if this merc is neutral/on same side, he's not an opponent
		if ( CONSIDERED_NEUTRAL( pSoldier, pOpponent ) || (pSoldier->bSide == pOpponent->bSide) )
		{
			continue;
		}

		// if this guy SAW an enemy recently...
		if( pSoldier->aiData.bOppList[ pOpponent->ubID ] >= SEEN_CURRENTLY && 
			pSoldier->aiData.bOppList[ pOpponent->ubID ] <= ubMax )
		{
			return( TRUE );
		}
	}

	return( FALSE );
}

Not sure on whether green is already taken, but why not use the full range from green to red for the name?

Come to think about it, with this one could remove the hard distinction between spy level 1 and 2 somewhat, and have the suspicion simply rise slower for an expert spy.

I'm not really a fan of the 'uncover spy automatically when in combat and we've seen any hostile', so I'm skipping that part.