The parties will evaluate the deal yearly, and some parties, especially the Social Liberals, have said that they want and expect a second referendum soon. One reason is that the Europol database will soon be searchable in portable devices carried by the police officers, but Denmark will not be able to use those due to the lack of direct access to the database. Also the lack of voting rights on Europol decisions means that Denmark, who is among the countries who use Europol the most, will not be able to influence decisions made about its structure and function.
No, it would most likely be one which includes full Europol-membership + participation in other regulations on crime-fighting, but without the part that allows Parliament to opt-in to new justice regulations without new referendums. All three parties who recommended a no primarily focused on this aspect of sovereignty, where they feared what parliament would sign Denmark up to in the future. They said that if the result became a no and Denmark could not get a satisfactory deal, then they would accept a new referendum without the sovereignty aspect and recommend a yes. A few weeks ago DPP withdrew that promise, because obviously the DPP would never go in to a referendum recommending a yes (see EU patent cooperation, which they supported until there was a referendum on it). The Liberal Alliance is in government now, so if the new referendum comes in this term, they will obviously go for yes. But even before entering government, they were sounding sympathetic to a new referendum and going for a yes. LA also made clear in the campaign, that they were not full-blown no, and often compared themselves to the Alternative whose slogan was "yes, but". LA was "no, but". The Red-Green Alliance is a bit harder to gauge, but they are not as dogmatic in their EU opposition as the DPP, and there is no new Eurosceptic party threatening them. They are very concerned about data protection, so they might go for a no if PNR is included. However, if the included regulations are more narrow (Europol and a few minor things), then I think they would not have a big problem in going for a yes.
If the technological advances in Europol happen as planned in the next years, then such a more narrow referendum is quite likely in a few years.
