There are some programs (mostly VPN) that claim that they have 2048-bit military grade encryption. Is this value highly exaggerated in the real world? Should we trust such claims? Or, should our suspicious level go up when we see such exaggerated value because that might be to attract customers?
2048-bit encryption is not exaggerated. This is a standard key length for asymmetric keys. See section 4 for more details on this. There is a key size difference between asymmetric keys and symmetric keys because asymmetric keys need the extra bits to be effective. Symmetric keys are smaller because the math allows it.
With VPNs you should be encryption in most cases with 2048-bit or 4096 RSA certificates, DHE-RSA-AES256-SHA for exchange of OpenVPN key material and AES-256-CBC-SHA for data. - See Volume III for VPN security.
What is exaggerated is the “military grade encryption” phrase as that has no meaning.