Opted for Zendesk
Anders,
I've persisted with osTicket, but I think that fundamentally you'd need a lot more control over the Exchange Server than we currently have with Office 365 to be able to integrate the email from osTicket.
Having done some further solution research I've opted to go ahead with Zendesk ($20 for the first year on the starter plan). I've been able to implement support emails with 365 by just using distribution groups and using an SPF record to allow zendesk to send emails from my domain.
It may not be a viable choice for you, but for $20 on year one its pretty hard to argue with. I've probably wasted more money than that with the time I've invested trying to resolve this issue with osTicket & Office 365.
I think the guys have done a great job with osTicket, but it just didnt fit my requirements!