Figured out the issue.
The 2nd approach works. The issue was with my invocation of the deleteAllQueuedMessages message. The method takes a boolean argument which indicates the messages should be moved to the Exception Destination. I was not passing this argument !!!
I corrected the implementation as below and it works now.
connection.invoke(objName, "deleteAllQueuedMessages", new Object[]{false}, new String[]{"java.lang.Boolean"});