I've set up direction LAN -> WAN, Source IP !mailserverIP, Destination IP ANY, Service Type - Created 2 Service Objects for port 25 and 465. Filter -> Block Immediately.

However there still seems to be SPAM being generated from on of the machines on the local network - is this set-up correct ?

Depends where the spam is originating and going. Check the headers to start.

We don't have any email we can look at - we only know there something wrong as we've been put on a blacklist for SPAM coming from our public IP address. It's not our main email server as this would have generated lot's of undeliverable mail - so it must be one of the other machines on our local LAN ?

I think you are jumping to conclusions.

How do you know SPAM is still being generated?

I'd suggest logging all mail traffic for a starter.