I'd like to add a method to my existing server's CORBA interface. Will that require recompiling all clients?
I'm using TAO.
Recompilation of clients is not required (and should not be, regardless of the ORB that you use). As Adam indicated, lookups are done by operation name (a straight text comparison).
I've done what you're describing with our ACE/TAO-based system, and encountered no issues (servers were in ACE/TAO C++, clients were ACE/TAO C++, C# using Borland's Janeva, and OmniORBPy).