I know that method lookups are cached, but I am quite certain (from the last time I read the documentation) that that cache is associated with the package STASH, rather than each object, since it logically applies to the class (package) and is shared between all objects of that class.
I would have to dig into the code to be sure, but the memory overhead for bless appears to be very minimal — once an SV has been upgraded high enough to carry any kind of magic, it also has a STASH pointer, and AV and HV structures are complex enough that they always have those fields.
Arrays in Perl do have considerably smaller overhead than hashes, although not a factor of 10. If you have a large number of some class of object, enough to cause memory usage problems, changing the internal representation to arrays and using constant to name the fields is likely to help. If encapsulation has been respected, this will require no changes outside of the object's implementation class.