Invalid versioned objects getting created

I have a problem which I believe is an extension of ORA-04043 issue. Whenever the database packages are deployed using 'CREATE OR REPLACE ..' option and then grants are given to the schemas to exec...