I've had a big long think about this all day long about the way I plan to implement this. The goal is to end up with a system that any SCP coder can use to add multiplayer functionality to any new SEXP simply by following a short list of rules. First I'll go into what I'd want everyone else to have to write when they make a new SEXP and then I'll explain how I'm thinking about making the code do that.
What I want to do is create a series of wrapper functions that can be called from the functions that actually do the work of making the SEXP work. They'll have a generic easily understood name like multi_send_ship, multi_send_object, multi_send_int, etc. Earlier I gave the example of the change-iff SEXP coded using this system so I'll stick to that. The code that actually changes the iff and does a multiplayer callback currently looks something like this
void sexp_ingame_ship_change_iff(ship *shipp, int new_team)
{
Assert(shipp != NULL);
shipp->team = new_team;
// send a network packet if we need to
if((MULTIPLAYER_MASTER) && (shipp->objnum >= 0))
send_change_iff_packet(Objects[shipp->objnum].net_signature, new_team);
}
Now if someone were coding the change-iff SEXP today it would be up to them to code in the send_change_iff_packet() packet into multimsgs.cpp themselves. Since only a few coders understand how that all works very few have bothered in the past. So we get new SEXPs that don't work in multiplayer.
Once I have the new stuff working though you'd be able to just code this.
void sexp_ingame_ship_change_iff(ship *shipp, int new_team)
{
Assert(shipp != NULL);
shipp->team = new_team;
// send a network packet if we need to
if((MULTIPLAYER_MASTER) && (shipp->objnum >= 0))
multi_start_packet();
multi_send_ship(shipp);
multi_send_int(new_team);
multi_end_packet();
}
You'd also have to code a new function for the player side.
void multi_sexp_ingame_ship_change_iff()
{
ship * shipp;
int team;
multi_get_ship(shipp);
multi_get_int(team);
Assert(shipp != NULL);
Assert(team = whatever check to see that it's a valid team);
shipp->team = new_team;
}
Hopefully I can make it work that easily.

Now for how I think it would be implemented.
First, add a global variable, set in eval_sexp() to hold the number of the SEXP operator. This prevents the coder needing to keep track of it.
Second, create a buffer to hold the data. It will need to be bigger than MAX_PACKET_SIZE so I'd suggest simply doubling that.
Third create a second buffer that holds the data type (standard ones like byte, short, etc but also a few other ones like vector, orient and string which the game already has functions for). The 2nd buffer will also hold include 3 special types OP, COUNT and TERMINATOR. OP means that the next value in the data buffer is the op_number for a SEXP (i.e it denotes that we're starting the data for a new SEXP). COUNT says how many pieces of data there will be in this next set and TERMINATOR means the end of a set of data (Basically a check that the data sent in COUNT hasn't overflowed).
With that done I can start on the real hard work.

void multi_start_packet() {
Write the SEXP_Operator number into the data buffer.
Write OP and then COUNT into the Type buffer.
Store the next data index as we'll need it later to write the COUNT.
}
void multi_send_int() {
Write the int into the data buffer (remembering to deal with endian issues).
Write INT into the Type buffer.
Increment the COUNT by 4 (i.e the size of an int).
Call the multi_sexp_maybe_send_packet() function.
}
void multi_end_packet() {
Write -1 into the data buffer.
Write TERMINATOR into the Type buffer.
Write the COUNT into the data buffer at the index we saved earlier.
Call the multi_sexp_maybe_send_packet() function.
}
void multi_sexp_maybe_send_packet() {
If the index of the data buffer isn't MAX_PACKET_SIZE yet, return.
If the last entry in the type buffer is a TERMINATOR then store the current index of the data array.
If not, iterate back through the types array until we find the last one and store the corresponding data index instead.
Write the data buffer until the stored index into a SEXP_UPDATE packet and send it to to the clients.
Slide down any entries after the stored index to the start of the array.
}
That should pretty much handle the server side of things. I'd need a check in game_simulation_frame() to make sure the buffer is flushed after mission_eval_goals() returns so that you don't have any data still sitting in the buffer until the next frame of course.
On the client side when a SEXP_UPDATE arrives it would read out the data into a buffer from the start of the packet until it has read out the number specified in the COUNT. It then checks that the next one is a TERMINATOR (i.e -1). If it's not then it will have to throw out the entire packet as there is no way to recover from that error.
If the packet is fine then it checks that the OP is valid. If it's not it throws out this SEXP and moves on to the rest of the packet (Thus giving us compatibility if the client has an older version of FSO than the server). If the OP is valid the game then calls a function similar to eval_sexp() but which figures out which function to call on the client ( multi_sexp_ingame_ship_change_iff() in the example above).
Anyone see any glaring flaws in the plan so far?