Hey,
I made great use of the policies of Cormyrians towards adventurers in my game. I think showing the effects of the local law on adventuring is a great idea, ESPECIALLY since it annoys the PCs. This game is about overcoming challenges, after all, and that shouldn't be restricted to monsters and traps. I'll make two suggestions that aided me in reducing player frustration (note: not CHARACTER frustration).
1) Give ad hoc xp for dealing with the law. Call it roleplaying rewards or whatever. Adventuring in Cormyr costs money/resources and time before the characters even step into the dungeon (or what have you). As such, they should be rewarded for following the books (especially the Lawful types). Maybe throw 'em a CR = party level for major accomplishments (such as obtaining the adventuring charter), and CR = party level-1 or 2 for getting the writs. Naturally, this means that the PCs can't just say "oh, we go and get the charter." It will need to be role-played out, with appropriate Diplomacy, Bluff, and Sense Motive checks.
2) Make sure to throw in a couple of examples of the law actually working as it should. The Cormyrian adventuring charters weren't set up in a vacuum, so they should work for the good of the people more often than not. The PCs should witness the Purple Dragons repelling some evil creature, arresting an adventuring group that did not acquire the proper writs (make sure that the NPC party is not worthy of sympathy), or even finally, if grudgingly, acknowledging the good that your PCs are doing. Perhaps the paladin might even be offered a position with the Purple Dragons?
Just some ideas. I hope they help.
-Matt