In the state of Oklahoma (where I live) it is legal to record a phone
call as long as  at least one of the parties knows.

I have downloaded a recorder for my nokia ngage that is supposed to
record calls to the phone, but it sends a beep tone every 5-6 seconds.

The company that makes the recording software says this is built into
the phone by nokia.

Any ideas if there is a way around this restriction, or if there is a
cellphone manufactured (by someone other than nokia obviously) without
this beep?

Thanks in advance for your opinions. Danny