Just looking for clarification :

Player A plays 'the Grand Melee' plot card so all players now count their STR based on the number of characters.

If during a melee game you pick up either the military,intrigue or power titles does this count towards the STR when attacking/defending ?

Thanks

Yes. The bonus from the titles modifies total challenge STR. There is nothing on the plot that says, or implies, that total challenge STR cannot be modified.