Given the choice between your sureness and the system message, I will 100% of the time believe the system over you -- sorry but the system just has no reason to lie about this. Could you have the data set open in ISPF (browse or edit)? That would cause "DATASET IN USE" messages.I am sure that my dataset was not opened any where even then the failure message says" DATASET IN USE".
Why not take the simple way out and just include a DD statement pointing to the file being renamed with DISP=OLD? That way the job won't even start running until the RENAME can succeed. The DD statement does not have to be used in the IDCAMS commands -- it is there merely so the system will grant exclusive access to the data set to your job.