We are using a cloud hosted router for our BGP announcements. Now we want to allow servers in a different DC to be able to use these IPs. We thought about using GRE tunnels for this which works great however there is the issue that due to the NAT we can't bind to the public IP directly. We thought about using BGP over GRE but the traffic is not routed to the server.

HI MatthiasMerkel... I prefer to design an internal OSPF network which can route my whole network (this may be done with Layer2circuits / EoIP / GRE Tunnels between all DC), once that you have OSPF working, you are able to configure BGP as an EGP, so you can use your publics IPs anywhere and them will be advertised only by BGP from each remote node to the main edge router, and to make it easier I will probably add 2 RouteReflectors in the middle.