I have a little complicated problem and I need some suggestions.

I am a web application programmer and I had a client in Germany. They bought domain name and web hosting at Strato. but it was so slow and their customer service was ridiculous. So I moved website to a server in United States.
I contacted to Strato to change DNS information but they said they don't offer dns change service. So I basically changed IPv4 and domain started to work with current server. Now it goes to new server but when you whois domain name, DNS is still shows strato.

But then we had email problem. hotmail and some other email providers started to block our outgoing emails. I contacted our server admin and he recommended to set up SPF but strato doesn't provide that service either and new server admin said he can do nothing because dns is not located on his server.

Now i don't know what to do. Any recommendation?