Hello,
You can have Backup Exec 9.x and 10.x with MSDE sp4 because till now we have no issues with the compatibility of this new service pack. But incase of issues you will have to contact Microsoft.
Please feel free to get back to us incase of further queries.
Note : If we do not receive your reply within two business days, this post would be marked ‘assumed answered’ and would be moved to ‘answered questions’ pool.
Thanks.