Is there an eligant way to make methods in perl really private?

You're got some good answers above. Here's a different approach.

You can get the delayed effect of private methods by adopting a simple convention: Start all private methods with an underscore, and teach people not to invoke these methods from outside of the class hierarchy¹. To enforce this, it's a simple matter to spider your code base looking for references to private methods that are not preceded by "$self->".

Having a script that traverses the code base looking for certain patterns can be very useful. In team settings, I've set up scripts to look for special code patterns (e.g., "TBD" or "FIXME" comments, correct copyright strings, etc.) The scripts ran every night, and produced a report (an HTML page) that we would check every morning. It also gave us an easy way to chart our code growth over time.

The question you'll need to ask yourself is whether you can live with the delay. I've found that the convention was good enough.

¹ Purists will note that this really enforced "protected" methods.