There is a rule against stickers and the like on the robot. What can I legally do to mark ownership of major LEGO parts?
The ban on stickers was instituted to prevent their use as structural elements and to keep the robots looking LEGO-ish. Although it is technically illegal, a small sticker with the team name on an RCX/NXT is not likely to cause problems. Make it small and obvious that it is not aiding in the structural design of the robot. Better yet (and now even legal!, see rule 5), use a Sharpie pen to write the identification mark in a hidden spot. Make it obvious that the mark in no way is affecting the behavior of the LEGO or the robot.