The key seems to be how evident it is that the person is recording. If it is at all not obvious to the police that a recording is being made, it is illegal. If you put a microphone or camera in their face however it is OK.
So the Rodney King tape would be illegal. In fact most police abuse tapes I can recall would be illegal, since people don't like to get very close to packs of violent officers.
I've been trying to find reliable sources that say one way or the other about Maryland (my current state of residence). Do you have any links? I did find this (http://www.rcfp.org/taping/states/maryland.html) which says that MD state courts have interpreted the law not to apply in public.
It will also end up being questionable considering USSC rulings on reasonable expectations of privacy in public settings. That is what surprises me considering this seems to fall squarely as 1st, 4th, 5th, 14th amendment issues.
And not just sort of illegal. Class 1 felony punishable 4-15 years in prison illegal.