Well, the server is a hosted root-server with a dedicated IP in a server-cluster. There are no real firewalls in that sense, all traffic is routed to my server.
Then, there´s the UFW firewall running inside my Ubuntu distro where I host the server. The UFW firewall is open for 16262 on UDP (as well as 16261).
NMAP or NetCat can be used to test UDP packets. You basically install it on the host that you´re trying to test, let it bind to port 16262 (that´s why the PZ server must be shut down) and then you try to send an udp packet using another netcat instance towards the server from a remote machine. If you see some inbound traffic you can be sure that the port is forwarded.
Anyways, I´ll try to disable the firewall completely on this host and check if the connection works then.
Thanks so far, if I have some finding I´ll report back, maybe it helps some other users.