Unit testing of stored procedures
We've been doing this for almost five years, and we think that explicitly testing modifications is definitely doable, but it is quite slow. 
Besides, we cannot easily run such tests concurrently from several connections, unless we use separate databases. Instead, we should test modfications implicitly - we use them to build up at least some of the test data, and verify that our selects return expected results.

I've written an article entitled Close Those Loopholes: Lessons learned from Unit Testing T-SQL, as well as some blog posts 

Regarding your question "Is there a treshold in complexity where it gets completely hopeless?", complex modules need tests much more than simple ones.

To simplify maintenance, we generate expected results, and we store them in separate files - that makes a huge difference.