I don't see why it's so difficult to believe. As noted on Mullvad's "Swedish legislation" page that you linked to, search of premises in a case like this is only allowed if there is a reasonable expectation of finding items subject to seizure (or other evidence of the offense in question). For what it's worth, the law itself is very readable, if you know Swedish [1].
Given that Mullvad are highly public about what data they store and why, Mullvad would arguably be able to make a strong case that there could be no such reasonable expectation. So the police had to weigh the potential gain of doing the search anyway against the risk of opening themselves up to lawsuits by doing so.
I would not have been surprised if they had decided to do it anyway, but I'm not really surprised at this outcome either.
Given that Mullvad are highly public about what data they store and why, Mullvad would arguably be able to make a strong case that there could be no such reasonable expectation. So the police had to weigh the potential gain of doing the search anyway against the risk of opening themselves up to lawsuits by doing so.
I would not have been surprised if they had decided to do it anyway, but I'm not really surprised at this outcome either.
1: https://lagen.nu/1942:740#K28P1S2