我们要给他什么礼物 should be fine.
送 is usually used with gifts rather than 给. Also be careful with the difference between 他 and 她. Here they specify "her", so it should be 她。
I would say that you would rather use 送 instead of 给 to emhasize the act of giving it for free as a gift, 给 simply means to give. Though your sentence is not incorrect.
Yeah thats true
Yao4 is should here?
"我们要送给她什么礼物？" is this possible?
Yes. That is how I normally say it.
Hello, is 我们要给她送什么礼物 correct ? It's refused.