Our client owns a server with a domain: website.com We have a server that our client points videos.website.com to. Emails sent from videos.website.com are getting flagged as spam because website.com doesn't have something saying that videos.website.com on a seperate server is allowed to send mail on behalf of website.com.
How do we fix this / set this up?
Chances are this is going to take a several DNS changes, what you want to use is a convention called Sender Policy Framework (SPF). This allows your site to tell other mail servers that your configuration is what you are expecting.
SPF could have it's own books written about it, but I've had good luck using online wizards for this kind of thing. Additionally, you're going to want to make sure PTR records are also setup in accordance with good mail-server practices (again, beyond the scope of a simple answer).
Here's a couple of SPF wizards to get you started:
Microsoft SPF Wizard
MTGSY SPF Wizard
Some basic information about mail servers and DNS. This site has a lot of good information on it if you go to "TOC" at the top
Mail Servers and PTR
All you need to do is add a:videos.website.com to the SPF record on the client's domain (you may need to get them to do that).
If they don't have an SPF record, you should set one, and include that item in it (see one of many available wizards for that).
That directive will tell receiving servers to look up the address of videos.website.com and allow those servers to send emails from the domain.
This doesn't have much to do with DKIM, though if the domain uses DKIM your mails should as well.
Another thing you can do is request a service account on the SMTP server for website.com and send the mails via it instead of sending them directly. That is sometimes easier, as it will relieve you of the responsibility of maintaining a good reputation for all your IP addresses.