I realize samtregar mentioned BEGIN, CHECK, INIT, and END as not being subroutines. That is, in fact, not the case. They are all special subroutines, and attempting to define one by that name will cause it to trigger as if you had left out the "sub" keyword. So, you were on the right track with them.

package Foo;
sub BEGIN { print "I am Foo, called in BEGIN!\n" }
[download]

Personally I'd avoid any subroutine name in all caps. For example, you missed all of the tie hooks (see perltie). I have seen modules (Class::InsideOut springs to mind) that will call all-caps subroutines in your modules, but it's chancy; the subroutine name may get hijacked by Perl at some point.