Another name for this automatic caching of function results is memoization. For a public interface, consider something along these lines:
public Func<T,TResult> Memoize<T,TResult>(Func<T,TResult> f)
... and simply use polymorphism to store T's in a dictionary of object.
Extending the delegate range could be implemented via currying and partial function application. Something like this:
static Func<T1,Func<T2,TResult>> Curry(Func<T1,T2,TResult> f)
{
return x => y => f(x, y);
}
// more versions of Curry
Since Curry turns functions of multiple arguments into functions of single arguments (but that may return functions), the return values are eligible for memoization themselves.
Another way to do it would be to use reflection to inspect the delegate type, and store tuples in the dictionary rather than simply the argument type. A simplistic tuple would be simply an array wrapper whose hashcode and equality logic used deep comparisons and hashing.
Invalidation could be helped with weak references, but creating dictionaries with WeakReference keys is tricky - it's best done with the support of the runtime (WeakReference values is much easier). I believe there are some implementations out there.
Thread safety is easily done by locking on the internal dictionary for mutation events, but having a lock-free dictionary may improve performance in heavily concurrent scenarios. That dictionary would probably be even harder to create - there's an interesting presentation on one for Java here though.