Legalities
I, too, am an attorney. I've briefed this issue (twice) before Courts in Oklahoma and written a paper for a Masters-level Telecommunications Management course.
We are talking about surreptitious recording, that is, recording when neither party is aware or consents or where only one party is aware and doesn't inform the other.
1) Surreptitiously recording a conversation to which you are not a party, the classic "wiretap", is illegal without a warrant. Period - setting aside Bush-era Patriot Act government warrantless wiretaps, which is a whole other thing.
2) As for surreptitious recording by one of the parties without the knowledge/consent of the other party - which seems to be the principle concern of this thread - Federal law permits it, generally, if the party consenting is the subscriber to the "line" that is recorded. So, from the Federal perspective, it's OK to record without informing the other party if you subscribe to the phone service being used. Note: this would make it OK to record ANY conversation on a line that you "own"... even if you aren't a party to the conversation. Example: Father recording calls, on his phone line, between his children and their mother, Father's ex-wife. SNEAKY! Note: That same call, recorded by Dad on his office phone, is probably illegal - unless Dad is self-employed and is the subscriber. If not, his employer's consent would be required, as it subscribes to the line recorded.
3) State law is broken down into "one-party consent" states and "two-party consent" states. As the name implies, and as has been correctly observed within this thread, some states require the consent of both parties before a recording can be made, others don't. Query: Can you record a call, that you initiate from a one-party state, if that call is made to someone in a two-party state? IMHO, no.
Also, a distinction of context should be made. Is the recording being used to refresh the recollection of a journalist, or otherwise used simply to perpetuate information? Then it could be illegal, but who will ever find out? and who cares? are questions that should be asked. But if one tries to have a recording entered into evidence in a Court of Law, well, that's a whole other thing, too.
Hope this helps.
Jay D