Personally, I don't like using class membership to determine whether an object is "ok" or not. I mean, someone could use Node as a base class, but override all the methods to do anything they want anyway, so what's the point of looking for it? I'd rather go with what is sometimes called duck typing. That is, if it walks like a duck, and talks like a duck, it must be a duck.
This is reminiscent of Java interfaces. The techniques to do Java-like interfaces in Perl that I know of rely on creating a base class in which all the mandatory methods die, which forces the children classes to implement them. With this approach, however, the simplest way to test for conformance to the interface would still be an isa-type test. See Java-style interfaces in Perl.
My main objection to simply testing for the ability to execute certain methods is that, except for the simplest interfaces, it is unlikely that a class will fully implement an interface, including giving the correct names to all the methods, without the author being previously aware of the specs for the interface. If the author is aware of the specs, and these specs are enforced through an interface-like class as described above, then they may as well stick this interface-class in the appropriate @ISAs, and use isa to check for compliance.