I had more or less accepted that the solution might be to install the whole BackupExec package from scratch once more (I have spent a few evenings with that task during the last years). So, convinced that there is nothing to loose, I searched through the Patch list of Veritas and found a patched called: BE4691RHF52 275909.exe dated 23.06.2005 wich is a SP2 security roll up.
I was able to install this one on top of my BE 9.1 SP2 installation, without receiving the silly erormessage regarding SP1.
After installing that patch and a reeboot, I immediately tried to install SP3 and at this time that worked also.
I believe there must be something with the remote server agents that is causing the trouble, because the patch force us to do a new agent installation the same way as SP3 does. Well, this is not a solution to the original SP3 problem, but for me it is kind of a work around. Maybe you can try it too?