I actually got a reply from AWS customer support for how to debug this, but it turns out the problem simply disappeared when we switched from using the new VPC setup for this purpose to older one someone else had setup.
Not entirely sure how the VPC and the surrounding settings differ, but at least this solves the issue for us.