> We've recently started
> using <a service provider> to filter incoming email as we were already
> using it as a backup MX and the extra layer of virus and spam filtering
> is attractive.
>
> I'm seeing some bad BATV recipients and recipients not recognised errors that I
> don't really understand because the recipients are valid.
I'd talk to your service provider.
BATV works by altering the 'return path' of outgoing mail in a way that only the sending server understands, so that if a bounce message arrives it can check that the destination address matches the correct altering method. Any bounce messages to other recipients are rejected. (A bounce message can be detected because it has a blank return path). This stops you receiving bounce messages that happen if a spammer fakes your domain as the sending domain and you'll receive gazillions of bounce messages for messages you didn't send.
So, in VPOP3, in Settings -> Message Authentication -> BATV, there's an option to enable BATV and a 'BATV Secret'. No one else knows the BATV secret.
When you send a message through VPOP3, VPOP3 changes the return path to 'prvs=<tag>=<original email address>' . The 'tag' is generated from the date and email address AND the 'BATV Secret'. Since no one else knows the BATV secret (using a mechanism specific to the server as well), it means that no one else can generate a valid BATV tag.
My *guess* is that the 'Recipient not recognised' errors for BATV encoded addresses are because VPOP3 generated the BATV tag and your service provider is checking it - but obviously they don't know the BATV mechanism/secret used by VPOP3, so they don't recognise it.
The 'Bad BATV recipient(s)' are because the apparent bounce messages (because the 'From' is blank) are not BATV encoded at all and your service provider is expecting them to be.
I *guess* you have to turn off the BATV support in VPOP3 and send all your outgoing mail through your service provider's SMTP relay servers so that their servers can BATV encode the return path, so their incoming servers will be able to validate it correctly. Alternatively, they may have an option to handle BATV targets they don't recognise and just validate the original email address part of the recipient.
But, you need to talk to your service provider because the problems are happening on their servers and they should know what to do.