This issue has been fixed and I'm publishing what was done in case this could help someone else out there.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
I found out that this error is a misleading error due to a jndi name used. The JNDI name used for "jboss.entity.manager.factory.jndi.name"(declared in persistence.xml) was in the pattern "java:/persistence/abc" Although the error message "Persistence not bound" it should have been "persistence/abc not bound". It could be some error of the error message generation.
So the actual error was jboss.entity.manager.factory.jndi.name(declared in persistence.xml) is not bound. I noticed that this JNDI lookup is done(by EhCache) at the start up time just before binding this persistence unit JNDI name.
Solution
------------
After adding the following property to persistence.xml(inside <properties> ) and applying JBoss patches the error went away.
<property name="hibernate.transaction.factory_class" value="org.hibernate.ejb.transaction.JoinableCMTTransactionFactory"/>