Certificate-based authentication of parties provides a powerful means for verifying claimed identities, since communicating partners do not have to exchange secrets in advance for authentication. This is especially valuable for roaming scenarios in future mobile communications where users authenticate to obtain network access—service access may potentially be based thereon in integrated approaches—and where the number of access network providers and Internet service providers is expected to increase considerably. When dealing with certificates, one must cope with the verification of complete certificate paths for security reasons. In mobile communications, additional constraints exist under which this verification work is performed. These constraints make verification more difficult when compared to non-mobile contexts. Mobile devices may have limited capacity for computation and mobile communication links may have limited bandwidth. In this paper, we propose to apply PKI servers—such as implemented at FhG-SIT—that allow the delegation of certificate path validation in order to speed up verification. Furthermore, we propose a special structure for PKI components and specific cooperation models that force certificate paths to be short, i.e., the lenghts of certificate paths are upper-bounded to certain small values depending on the conditions of specific cases. Additionally, we deal with the problem of users who do not have Internet access during the authentication phase. We explain how we solved this problem and show a gap in existing standards.