Unsure about sending to an IP, but that's what I was talking about with DNS and MX record issues.
You can use this to find out what your MX records are:
http://mxtoolbox.com/SuperTool.aspx?...algarypuck.com
Then you could get one of the users to run this command from a command line inside their network (i.e. the network that their outgoing mail server runs in).
nslookup -type=mx calgarypuck.com
If the IPs jive then something else is going on. Or there's a network issue between their network and Google's mail servers.
If their outgoing mail server is elsewhere than on the same local network as their computers, you'll have to engage their IT support to start investigating.