Method lookup caching doesn't happen until a method has actually been called. Because the @ISA manipulation happens in a BEGIN block, this should occur before any method calls, thus before any method lookups have been cached.
Also, according to perlobj any changes to @ISA should invalidate the cache. There may be bugs lurking somewhere in perl's method lookup caching mechanism, but none that seem to be triggered by the technique I've discussed.
After all, the situation where package $X manipulates package $Y's <c>@ISA at BEGIN-time is really common. (Consider the case where $X eq "base" or $X eq "parent". Sure, this is happening at package $Y's request, but from Perl's perspective the same thing is happening.)
With Moose it happens at run-time, and this doesn't seem to cause any problems.