Verify paper wallets I generated a paper wallets with offlineaddress.com. Is there a way to check if the private key corresponds to the public key without compromising the wallet by loading it onto an online computer?
First off, only trust highly-reputable software to generate private keys, especially if they're web-based. It seems like this software has only 16 stars on GitHub and only 2 contributors: https://github.com/mikewoods/OfflineAddress.com

To answer your question, the only way to verify that a private key corresponds to the public key is to actually run the algorithm on a computer. My best advice here is to use a computer that is offline and that boots a highly-reputable open source operating system.