I've been running a VPN (currently WireGuard, previously StrongSwan) on a VPS through https://www.vultr.com/ for a little over a year now and have had no issues with the App Store. Signed-out Google Search, however, is a different story...
Do you know any good guides on configuring server to act as a vpn/proxy (routing mostly)? Regular wireguard articles don't cover this use-case at all, assuming reader know everything beforehand
For what it's worth, the RELATED, ESTABLISHED rule in FORWARD is a bad thing to forget; I was getting all sorts of interesting ICMP timeout errors because I didn't have it.
New connections from clients were allowed, but I didn't have a rule to allow related and established, which made some things work, but mostly not.