How to ensure that database cleanup is always performed after a test?

There are two ways to do this. One is using TestInitialize and TestCleanup attributes on methods in the test class. They will always be run before and after the test, respectively.

Another way is to use the fact that test failures are propagated to the test runner via exceptions. This means that a try { } finally { } block in your test can be used clean up anything after an assert fails.

[TestMethod]
public void FooTest()
{
  try
  {
     // setup some database objects
     Foo foo = new Foo();
     Bar bar = new Bar(foo);
     Assert.Fail();
  }
  finally
  {
     // remove database objects.
  }
}

The try/finally cleanup can get really messy is there are a lot of objects to cleanup. What my team has leaned towards is a helper class which implements IDisposable. It tracks what objects have been created and pushes them onto a stack. When Dispose is called the items are popped off the stack and removed from the database.

[TestMethod]
public void FooTest()
{
  using (FooBarDatabaseContext context = new FooBarDatabaseContext())
  {
    // setup some db objects.
    Foo foo = context.NewFoo();
    Bar bar = context.NewBar(foo);
    Assert.Fail();
  } // calls dispose. deletes bar, then foo.
}

This has the added benefit of wrapping the constructors in method calls. If constructor signatures change we can easily modify the test code.

I think the best answer in situations like this is to think very carefully about what you are trying to test. Ideally a unit test should be trying to test a single fact about a single method or function. When you start combining many things together it crosses over into the world of integration tests (which are equally valuable, but different).

For unit testing purposes, to enable you to test only the thing you want to test, you will need to design for testability. This typically involves additional use of interfaces (I'm assuming .NET from the code you showed) and some form of dependency injection (but doesn't require an IoC/DI container unless you want one). It also benefits from, and encourages you to create very cohesive (single purpose) and decoupled (soft dependencies) classes in your system.

So when you are testing business logic that depends on data from a database, you would typically use something like the Repository Pattern and inject a fake/stub/mock IXXXRepository in for unit testing. When you are testing the concrete repository, you either need to do the kind of database cleanup you are asking about or you need to shim/stub the underlying database call. That is really up to you.

When you do need to create/populate/cleanup the database, you might consider taking advantage of the various setup and teardown methods available in most testing frameworks. But be careful, because some of them are run before and after each test, which can seriously impact the performance of your unit tests. Tests that run too slowly will not be run very often, and that is bad.

In MS-Test, the attributes you would use to declare setup/teardown are ClassInitialize, ClassCleanUp, TestInitialize, TestCleanUp. Other frameworks have similarly named constructs.

There are a number of frameworks that can help you with the mocking/stubbing: Moq, Rhino Mocks, NMock, TypeMock, Moles and Stubs (VS2010), VS11 Fakes (VS11 Beta), etc. If you are looking for dependency injection frameworks, look at things like Ninject, Unity, Castle Windsor, etc.