Почему в C# есть такое странное ограничение на реализацию internal интерфейса?
Потому что interface по определению содержит описание только public членов.
Используйте явную реализацию метода интерфейса:
void IFoo.foo()
{
	throw new NotImplementedException();
}
Вызов:
Foo obj = new Foo();
((IFoo)obj).foo();
«Члены интерфейсов автоматически являются открытыми, и они не могут включать никакие модификаторы доступа.»
msdn.microsoft.com/ru-ru/library/ms173156.aspx