Removing the channel from the channels user is protected on will remove them from the list unless there is another channel remaining. So loop through the protect list and remove the channel you just parted.
When you part a channel...
Code:
on me:*:part:#:{
  var %i = 1
  while $protect(%i) {
    if $istok($protect(%i).type,#,44) { protect -r $protect(%i) # }
    else inc %i
  }
}


When you quit, you can use the disconnect event to to loop through all open channels, and remove the matches.
Code:
on *:disconnect:{
  var %i = x
  while $chan(%x) {
    var %i = 1,%c = $v1
    while $protect(%i) {
      if $istok($protect(%i).type,%c,44) { protect -r $protect(%i) %c }
      else inc %i
    }
   inc %x
  }
}


I think you'd be better off using raw 366 (End of names list) to populate your protects. (At the time you join a #, mIRC doesn't yet know if any other users are in the room, that info only comes from the names list, which is also where mIRC learns who (if anyone) is opped/voiced/etc.
Code:
raw 366:*:checkregs $2
alias checkregs {
  var %i = 1
  while $nick($$1,%i,$prefix) {
    protect $v1 $1 2
    inc %i
  }
}