I have seen simialar problems with sqlmaint and it is due to something happening to the .dll in memory, thats why restart of agent is re-setting it.

Possible options:

server reboot

copy the DLL over from another server thats ok

upgrade to SP4 could help you if this .dll is replaced by the upgrade