First of all, as you realize, it's not enough to use InternalsVisibleTo - you would also need to sign and strongly-name each assembly to ensure someone can't just spoof the name.
Now that that's out of the way, you would have to develop a challenge-response implementation on your own - this isn't something you can do unless you're willing to use the InternalsVisibleTo approach that you explicitly describe you don't want to use.
In a C-R model, you would need to pass some kind of token with every method call (or perhaps just to instantiate an object). The token would be a class that only your code can create an instance of - I would make this an internal class of the assembly you want to consume and make it accessible with InternalsVisibleTo - this way only a single class needs to be managed:
// SharedAssembly.dll
// marks ConsumingAssembly.dll as having access to internals...
internal sealed class AccessToken { }
public class SecuredClass
{
public static bool WorkMethod( AccessToken token, string otherParameter )
{
if( token == null )
throw new ArgumentException(); // you may want a custom exception.
// do your business logic...
return true;
}
}
// ConsumingAssembly.dll (has access via InternalsVisibleTo)
public class MainClass
{
public static void Main()
{
var token = new AccessToken(); // can create this because of IVT access
SecuredClass.WorkMethod( token, "" ); // tada...
}
}
You may want to put the AccessToken class in a third assembly that both the service provider and consumer know about so that you don't have to constantly maintain a different group for access token classes for different assemblies.
Building a C-R mechanism for every method is cumbersome and tedious. It also isn't 100% foolproof - someone with enough time and patience could probably find a way around it.
The best option (which may or may not be possible in your case) would be to keep your private code on your own servers and only expose it as a webservice (or something similar). This allows you to actively manage accessiblity to your IP and allows you to update who has access in a centralized (rather than distributed) manner. Technologies already exist to restrict access to web services using certificates, message-signature, and encryption. This would be the most reliable (and proven) way to control access to you IP.