I thought $Bin (or any variable) could only be untainted through a regular expression.

Correct. (Well, not quite. But I don't see how the other way documented in perlsec - see also Re: When not to use taint mode - could do anything to improve security.)

Is it something in lib that will be untainting it?

No, and lib would be the wrong place for automatic untainting. How should lib know which paths are secure and which ones aren't? How should lib know which string is a valid path, and which is not? At least lib would have to accept a regular expression to validate and untaint paths. (This is what File::Find does for the untaint and untaint_pattern options.)

Note the wording in the previous paragraph: a regular expression to validate and untaint. You don't just want to blindly untaint. You want to validate the input. Untainting of the input is just a welcome side effect of the validation.

By the way: you generally want a positive rule, describing how valid input looks like. You don't want negative rules that forbid invalid inputs. Simply because it is too easy to forget some invalid input.

Alexander