The Danes have tried this - and it did not work.
Basically, they have had this level of mass surveillance for a long time, and it has not helped at all. It is clear that this level of monitoring of citizens does not meet the objectives stated, and this example should be considered carefully by the UK while debating the Draft Investigatory Powers Bill.
(Thanks to Jesper Lund on twitter for pointing me to that article)
I also have to question some of the examples - Theresa May talked of an example of an abducted child and how it is crazy that if there was communications by phone or text before that, it could help investigation, but not if by social media. The proposed bill would show, for example, that the entire household has people connected to Facebook all day, or twitter, etc. It would not show which computers or even phones (on WiFi) in the house were connected, or if the child had any accounts on social media. The police would have to ask parents for details and then ask social media sites for details. The Internet Connection Records would not actually help with that.
However, given the extent that computers communicate behind the scenes, and the fact that a whole house will normally share the same IP address*, and that there may be unknown users on WiFi from the house, and DNS relays in daft routers, and viruses, and Tor, and so on, it is clear that apparent "Internet Connection Records" may be unrelated to individuals in the house. There is massive scope for misdirection. That is before anyone considers legally poisoning the database with deliberate bogus connections.
* Typically share a single IPv4 with NAT on the router which is not logged, or have an IPv6 prefix with privacy addressing meaning you cannot attribute a connection to a device.
Someone else pointed out that surveillance only really works when the people being spied on don't know it. If criminals know that all Internet connections are logged, they can be more careful with what they do - perhaps even reverting to paper! This leaves only the innocent having their privacy invaded for no real benefit - just look at the example of Denmark and learn from that lesson!
It is also worth looking at France which does a lot of surveillance as well - it clearly did not help, and I feel sorry for those that lost their lives due to the action of criminals.
Someone actually asked if I was arguing from a cost/complexity point of view as an ISP, or from a privacy and moral point of view. To some extent it is both, but as an ISP, if the government gave us a retention order, they would pretty much have to pay us to make that happen (though there is some debate on the extent of cost recovery). So from that point of view it is not really an issue - indeed, as we make routers and firewalls we have the scope to make a killing selling kit to provide the monitoring solutions to companies even. We aren't doing that! The issue really is that I think it is wrong to treat the population as criminals, and disproportionally spend public money reacting to terrorism and giving in to the terror in the way we do. We need to consider this like any other crime and tackle it sensibly and not with knee-jerk headline-grabbing "something must be done" crap. I hope that makes my views a bit clearer...
P.S. There is one thing that perhaps Theresa May has not considered. After an attack it is very bad PR for government and intelligence agencies if you can say "But they had them under surveillance and still did nothing to prevent this". Once you have everyone under surveillance, people can always say that after every incident.