(NoSuchVersion) when calling the GetObject operation: The specified version does not exist

I am trying to download all the versions of a file in Amazon S3 using boto3 (version 1.34.113) but it keeps giving the error botocore.exceptions.ClientError: An error occurred (NoSuchVersion) when calling the GetObject operation: The specified version does not exist.

My Python code is

import boto3

S3_BUCKET = "mybucket"
S3_KEY = "mykey"
s3_client = boto3.client("s3")
paginator = s3_client.get_paginator("list_object_versions")
page_iterator = paginator.paginate(Bucket=S3_BUCKET, Prefix=S3_KEY)
for page in page_iterator:
    for version_obj in page.get("Versions", []):
        version_details = s3_client.get_object(
            Bucket=S3_BUCKET, Key=S3_KEY, VersionId=version_obj["VersionId"]
        )

It is able to list down the versions but is not able to perform the get_object operation.

Troubleshooting I have done:

1. I have full S3 access. (s3:* on * resource)
2. My credentials are setup properly local.
3. I am able to list and download the versions from the AWS Console S3 interface.
4. The issue is happening for only a few files.
5. The S3 key is not a prefix to any other object ruling out the possibility of a key mismatch since list versions uses a Prefix and get object uses a Key.
6. AWS S3 CLI (version aws-cli/2.15.43 Python/3.11.8 Linux/6.8.0-48-generic exe/x86_64.ubuntu.24 prompt/off) works fine aws s3api list-object-versions --bucket mybucket --prefix mykey and aws s3api get-object --bucket mybucket --key mykey --version-id versionidfromresponseabove outfile.
7. The file is not deleted.
8. The version is not deleted.

The issue was probably with boto3. As per the suggestion from @jarmod, simply updating the package resolved the issue. However, downgrading back to v1.34 also did not result in the issue.