The first story is from last September - God knows how I missed it back then - and about the Catacombs under Paris. Apparently French police found a fully equipped cinema and restaurant in an uncharted section of the network! Working electricity, phone lines and all! The security measures the group who ran it were pretty impressive too.
In A Secret Paris Cavern, The Real Underground Cinema (The Independent; Wednesday 8th September 2004)
French Cinephiles Go Underground (BBC News Online; Thursday 9th September 2004)
The second story is from July of this year about a 25 mile network discovered in Moscow. Manhole Covers Hide Secret Moscow (BBC News Online; Tuesday 5th July 2005)