Your users can still screw it up by not calling the parent class new() method (if they overload new()). One strategy you may want to use instead may be to use your parent package's import() method to find out what packages are using the parent package, then inspecting their @ISA to see if they're inherited, and then grabbing the information from their symbol table. Assuming they don't dynamically create subs after BEGIN time, this should work fine.

You may also want to check for AUTOLOAD and DESTROY. Also, you can disable strict checking for a tiny scope:

sub mk_provides {
  no strict 'refs';
  # rest of the sub
}
[download]

and the strictness will be turned off for just the scope of the sub mk_provides.

update: added comment about inheritance.