I have the habit of always trying to differentiate application level code from framework level code, so I have encountered the problem that you are describing quite often: you usually want all the framework level code to be tested before any application level code begins to be tested. Also, even within framework level code, there tend to be some fundamental framework modules that are used by all other framework modules, and if something fails in the fundamentals, there is really no point in testing anything else.
Unfortunately, purveyors of testing frameworks tend to have somewhat rigid ideas about how their creations are meant to be used, and are rather protective of those ideas, while the people who use their frameworks tend to accept the intended usage without questioning. This is problematic, because it stifles experimentation and innovation. I don't know about everyone else, but I would prefer to have the freedom to try to do something in an odd way, and see for myself whether the results are better or worse than the established way, rather than not having the freedom to do things my way in the first place.
So, in my opinion, test dependencies would be an awesome thing to have, and in lieu of that, the ability to specify the order in which tests will be executed would be the next best thing.
The only way I have found to address the issue of ordering tests is by careful naming, so as to exploit the tendency of testing frameworks to execute tests in alphabetical order.
I do not know how this works in Visual Studio, because I have yet to do anything involving extensive testing with C#, but in the Java side of the world it works as follows: Under the source folder of a project we usually have two subfolders, one called "main", containing the production code, and one called "test", containing the testing code. Under "main" we have a folder hierarchy which exactly corresponds to the package hierarchy of our source code. Java packages roughly correspond to C# namespaces. C# does not require you to match the folder hierarchy to the namespace hierarchy, but it is advisable to do so.
Now, what people usually do in the Java world is that under the "test" folder they mirror the folder hierarchy found under the "main" folder, so that each test resides in the exact same package as the class that it tests. The rationale behind this is that quite often the testing class needs to access package-private members of the class under test, so the testing class needs to be in the same package as the class under test. In the C# side of the world there is no such thing as namespace-local visibility, so there is no reason to mirror the folder hierarchies, but I think that C# programmers do more or less follow the same discipline in structuring their folders.
In any case, I find this whole idea of allowing the testing classes to have access to package-local members of the classes under test misguided, because I tend to test interfaces, not implementations. So, the folder hierarchy of my tests does not have to mirror the folder hierarchy of my production code.
So, what I do is that I name the folders (meaning, the packages) of my tests as follows:
t001_SomeSubsystem
t002_SomeOtherSubsystem
t003_AndYetAnotherSubsystem
...
This guarantees that all the tests for "SomeSubsystem" will be executed before all tests for "SomeOtherSubsystem", which in turn will all be executed before all tests for "AndYetAnotherSubsystem", and so on, and so forth.
Within a folder, individual test files are named as follows:
T001_ThisTest.java
T002_ThatTest.java
T003_TheOtherTest.java
Of course, it greatly helps that modern IDEs have powerful refactoring capabilities which allow you to rename entire packages (and all sub-packages, and all code that references them) with just a couple of clicks and keystrokes.
