I can't suggest - I'm not a hosting company!
However, here's the evidence:
1. Domainkeys and SPF records now in place - For which, thanks very much
2. Mail from gmail accounts TO Yahoo accounts is delivered consistently and immediately.
3. Mail FROM Yahoo accounts TO gmail accounts and eukhosted accounts is delivered immediately and consistently.
4. Mail from eukhosted domains is delivered intermittently - either not at all or with delays.
So, if we take each piece of evidence -
1. The problem cannot be solely due to lack of domainkeys and SPF records, since (a) the issue has not improved since adding them and (b) mail from liverpool was still delivered, albeit intermittently, despite having no SPF records or Domainkeys. A possibility here is that the domainkeys authentication procedure doesn't actually work properly, or is broken atm!
2. GMail is delivered straight away - afaik, there is no difference between eukhost mail and gmail now that eukhost mail has SPF and domainkeys. So, it can't just be a traffic-jam problem TO Yahoo accounts - otherwise, gmail would be delayed too.
3. Since nobody has reported sending problems FROM Yahoo, we can assume it's not a Yahoo SMTP error, or an error with eukhost receiving mail.
4. What's left? - Yahoo is delaying mail BUT ONLY from none gmail accounts, or eukhost accounts. Does that seem feasible to anyone? I'm not being clever here - I simply don't know. The only other possible option to explore, from eukhost's POV, is whether its SMTP servers are suffering from heavy traffic that's causing delays? Again, I'm no expert. Just going on a process of elimination.
And to just to emphasise Mark - i'm really not having a go at Eukhost here - In fact I applaud your efforts to sort things out. If the Merchant Bankers at Yahoo had done the same, then I'm sure the both of you would have resolved this by now!