Question:

Why does the offline validation rule, that is using Is_Parent_Call_vod__c, not immediately firing when conditions are met?

Answer:

Is_Parent_Call_vod__c is a formula field.  The formula results are evaluated at sync time.

Consider using the Parent_Call_vod__c within the Offline validation rule instead of Is_Parent_Call_vod__c.

Related Documentation:

CRM Help Documentation: Offline Validation Rules