I think that did the trick!
I purged a few messages from the Internet Gateway, stopped Scalix (unix.in processes would not die gracefully). Restarted Scalix and all the messages were sent OK. Appears to be working fine.
Thanks Shredder for helping out - I guess for me learning under pressure is sometimes a good thing :)
Right now omscan.server is running at high CPU - I guess its doing cleanup and integretiy check on the store (?) Not sure what that process does - I'll have to read the manual