Ensuring Theme Compatibility with Multisite Blogs

In preparation for launching my blog network, I’m trying to expand my library of available themes beyond the many great themes available on WPMU Dev. I’ve been able to figure out a strategy for tackling some of the security concerns related to theme options that might allow users to insert unfiltered code (thanks Phil), but I’m curious about general compatibility issues. In a nutshell, I’m not sure exactly what makes a theme multisite compatible (or not).

Are all themes assumed to be compatible due to the inherent design of WordPress 3.x? If not, are there particular lines of code that need to be present to ensure compatibility?

In the event that compatibility can only be determined through rigorous testing, could you provide a list of use cases/scenarios that I should be testing?