It is my understanding (I am not a lawyer, but related to enough of them that I hear this all the time) that in the Commonwealth of Virginia, only one of the parties on the phone needs to know the call is being recorded. So, you could always fly to VA and make the call.

I am not sure how the FCC Code (if there is such a thing, I am talking out of my league here) fits in. I have heard of a few cases where conversations recorded in VA were allowed to be entered into evidence in VA courts. Perhaps Greg99 could do a Lexus Nexus on this?