netcup & racknode are the ones that come to mind. I know europe has better prices than USA for dedis because I ran across them a lot when looking for a dedicated provider. But I haven't committed them to memory as I'm a USA customer.
None will be cheaper than a heztner dedi but will cheaper than this large VPS + block storage VPS idea. To OP, give Heztner dedi a chance and if they are saying they need to put you on a new server do that.
Worldstream is one I tested for a backup server outside USA but only for about a month. Their international speed was poor (for huge file transfers) and they were honest about probably not being the best option for me and gave a refund without problems. I imagine their European network is way better