Clustering Observations by String Sequences (Python/Pandas df)
As URLs are usually unique strings, I am not sure if NLP methods are proper things here. That is interesting that TFIDF+Kmeans gave you an intuitive results however as the problem is unsupervised, it´s pretty difficult to say what is intuitive that way. 

In my opinion your problem is a typical Community Detection in Bipartite Graphs e.g. this paper. This approach is certainly worth to try. Of course the result can be combined with other algorithms e.g. in a voting schema.

The last but not the least is to take a clustering method which does not limit to resolution e.g. in Community Detection, any Modularity-based method is only able to capture clusters larger than a resolution limit. One approach to this is a hierarchical approach to partitioning the data in which you again apply clustering on the significantly large cluster you find.

Hope it helps!