Back in the good old days, pod2man would complain if you would not have a NAME section (excpet if you used the --lax option). All my documentation starts with NAME, SYNOPSIS and DESCRIPTION, as good manual pages do. For me, POD is primary used to generate man pages, and hence, it should follow the man pages conventions, hence the first three sections. And while in extreme cases a SYNOPSIS or a DESCRIPTION may be omitted, NAME would not be optional.

As for other sections, BUGS, SEE ALSO, COPYRIGHT/LICENSE, AUTHOR/MAINTAINER, and HISTORY, I use frequently. To a lesser extent: EXAMPLES, FILES (if additional files, typically configuration files, are used by the program), STANDARDS (if it conforms to standards), REFERENCES (for instance, to literature).

I presume that you list methods in a section METHODS. I would describe methods in the DESCRIPTION section. I've no idea what to expect from sections named PUBLIC and PRIVATE.

Private methods or subroutines can be commented rather than POD-ed, but their names should follow the leading underscore convention so they can be easily excluded from any coverage calculations.

I would not document private methods in the POD - as I said, for POD is to generate manual pages. That is, user documentation. It should document the interface: what to pass in to the program, subroutines or methods, and what to expect to happen in return (return values, side-effects). Discussion of the internals should be kept to a minimum, and only done if relevant. Hence, no private methods.

I don't like having a (potentially) large number of subroutines starting with an underscore. It looks unnatural and distracts. Doing so for the reason you mention is double bad. Programming languages shouldn't force arbitrary rules upon a programmer - it's the programming language that should be the slave, and the programmer the master. Not the other way around.