I don't think there was an Underboss, and even if there was one, it definitely wasn't Paulie. I don't think the writers were too worried about that kind of thing. The show was geared to a more general audience and the average person wouldn't pick up on whether or not there was an Underboss.

And for what it's worth, in the 2nd to last episode, New York decided that Tony, Silvio, and Bobby were the top 3.