Why is this happening when I add a Subdivision Surface Modifier, and why exactly at those spots, all edges seem equal to me.
I think you will find the reason for this, is that the vertices are not actually attached. In edit mode, go to vertex selection mode, and press spacebar, type "remove doubles" and click the remove doubles operator.
If that does not work out, do what you can to investigate where vertices do not actually connect.
Also keep in mind that subdivision modifier works best with quads. You may want to do your best to convert those triangle faces to quad faces.
$\begingroup$ This helped me in finding out that there are indeed a lot of duplicate vertices. This is a converted and imported model and it seems it consists of multiple unconnected parts, mapped to different uv sections. So either removing or merging the vertices screws up the uv mapping so it looks like i have to leave it as is. Thanks $\endgroup$– Fish013Aug 14, 2015 at 19:45
Select the edge which seem to have deleted faces around and press ShiftE To increase the crease, this should solve the problem.