The issue of dependencies when initiating a new view model can be handled with IOC.

public class MyCustomViewModel{
  private readonly IShoppingCartWebService _cartService;

  private readonly ITimeService _timeService;

  public ProductDTO ProductDTO { get; set; }

  public ProductDetailsViewModel(IShoppingCartWebService cartService, ITimeService timeService){
    _cartService = cartService;
    _timeService = timeService;
  }
}

When setting up the container…

Container.Register<IShoppingCartWebService,ShoppingCartWebSerivce>().As.Singleton();
Container.Register<ITimeService,TimeService>().As.Singleton();
Container.Register<ProductDetailsViewModel>();

When you need your view model:

var viewmodel = Container.Resolve<ProductDetailsViewModel>();
viewmodel.ProductDTO = myProductDTO;

When utilizing a framework such as caliburn micro there is often some form of IOC container already present.

SomeCompositionView view = new SomeCompositionView();
ISomeCompositionViewModel viewModel = IoC.Get<ISomeCompositionViewModel>();
ViewModelBinder.Bind(viewModel, view, null);

Short answer for your questions:

1. Yes State+Behavior leads to those problems, but this is true for all of OO. The real culprit is the coupling of ViewModels which is a kind of SRP violation.
2. Statically typed, probably. But you should reduce/eliminate your need for instantiating ViewModels from other ViewModels.
3. Not that I’m aware off.
4. No, but having ViewModels with unrelated state & behavior (Like some Model references and some ViewModel references)

The long version:

We’re facing the same Problem, and found some things that may help you. Although I do not know the “magic” solution, those things are easing the pain a little.

1. Implement bindable models from DTOs for change tracking and validation. Those “Data”-ViewModels must not depend upon services and do not come from the container. They can be just “new”ed up, passed around and may even derive from the DTO. Bottomline is to implement a Model specific to your application (Like MVC).

2. Decouple your ViewModels. Caliburn makes it easy to couple the ViewModels together. It even suggests it through its Screen/Conductor model. But this coupling makes the ViewModels hard to unit test, create a lot of dependencies and most important: Imposes the burden of managing the ViewModel lifecycle upon your ViewModels.
   One way to decouple them is using something like a navigation service or ViewModel controller. E.g.

   public interface IShowViewModels
   {
   void Show(object inlineArgumentsAsAnonymousType, string regionId);
   }

Even better is doing this by some form of messaging. But the important thing is not to handle the ViewModel lifecycle from other ViewModels.
In MVC Controllers do not depend on each other, and in MVVM ViewModels should not depend on each other. Integrate them through some other ways.

3. Use your containers “stringly”-typed/dynamic features. Although it could be possible creating something like INeedData<T1,T2,...> and enforcing type-safe creation parameters, it is not worth it. Also creating factories for each ViewModel type is not worth it. Most IoC Containers provide solutions to this. You’ll get errors at runtime but the de-coupling and unit testability is worth it. You still do some kind of integration test and those errors are spotted easily.

The way I usually do this (using PRISM), is each assembly contains an container initialisation module, where all the interfaces, instances are registered on startup.

private void RegisterResources()
{
    Container.RegisterType<IDataService, DataService>();
    Container.RegisterType<IProductSearchViewModel, ProductSearchViewModel>();
    Container.RegisterType<IProductDetailsViewModel, ProductDetailsViewModel>();
}

And given your example classes, would be implemented like this, with the container being passed all the way through. This way any new dependencies can be added easily as you already have access to the container.

/// <summary>
/// IDataService Interface
/// </summary>
public interface IDataService
{
    DataTable GetSomeData();
}

public class DataService : IDataService
{
    public DataTable GetSomeData()
    {
        MessageBox.Show("This is a call to the GetSomeData() method.");

        var someData = new DataTable("SomeData");
        return someData;
    }
}

public interface IProductSearchViewModel
{
}

public class ProductSearchViewModel : IProductSearchViewModel
{
    private readonly IUnityContainer _container;

    /// <summary>
    /// This will get resolved if it's been added to the container.
    /// Or alternately you could use constructor resolution. 
    /// </summary>
    [Dependency]
    public IDataService DataService { get; set; }

    public ProductSearchViewModel(IUnityContainer container)
    {
        _container = container;
    }

    public void SearchAndDisplay()
    {
        DataTable results = DataService.GetSomeData();

        var detailsViewModel = _container.Resolve<IProductDetailsViewModel>();
        detailsViewModel.DisplaySomeDataInView(results);

        // Create the view, usually resolve using region manager etc.
        var detailsView = new DetailsView() { DataContext = detailsViewModel };
    }
}

public interface IProductDetailsViewModel
{
    void DisplaySomeDataInView(DataTable dataTable);
}

public class ProductDetailsViewModel : IProductDetailsViewModel
{
    private readonly IUnityContainer _container;

    public ProductDetailsViewModel(IUnityContainer container)
    {
        _container = container;
    }

    public void DisplaySomeDataInView(DataTable dataTable)
    {
    }
}

It’s quite common to have a ViewModelBase class, which all your view models are derived from, which contains a reference to the container. As long as you get into the habit of resolving all view models instead of new()'ing them, it should make all dependency resolution a lot simpler.

I work daily with ASP.NET MVC and have worked on a WPF for over a year and this is how I see it:

MVC

The controller is supposed to orchestrate actions (fetch this, add that).

The view is responsible for displaying the model.

The model typically encompasses data (ex. UserId, FirstName) as well as state (ex. Titles) and is usually view specific.

MVVM

The model typically only holds data (ex. UserId, FirstName) and is usually passed around

The view model encompasses the behavior of the view (methods), its data (model) and interactions (commands) – similar to the active MVP pattern where the presenter is aware of the model. The view model is view specific (1 view = 1 view model).

The view is responsible for displaying data and data-binding to the view model. When a view is created, usually its associated view model is created with it.

What you should remember is that the MVVM presentation pattern is specific to WPF/Silverlight due to their data-binding nature.

The view typically knows which view model its associated with (or an abstraction of one).

I would advise that you treat the view model as a singleton, even though it’s instantiated per view. In other words, you should be able to create it via DI via an IOC container and call appropriate methods upon it to say; load its model based on parameters. Something like this:

public partial class EditUserView
{
    public EditUserView(IContainer container, int userId) : this() {
        var viewModel = container.Resolve<EditUserViewModel>();
        viewModel.LoadModel(userId);
        DataContext = viewModel;
    }
}

As an example in this case, you wouldn’t create a view model specific to the user being updated – instead the model would contain user specific data that gets loaded via some call on the view model.

Sometimes it’s good to go to the simplest definition rather than a full-blown example:
http://en.wikipedia.org/wiki/Model_View_ViewModel
maybe reading the ZK Java example is more illuminating than the C# one.

Other times listen to your gut instinct…

Is having a lot of ViewModels with both state/behavior a design smell?

Are your models are object per table mappings? Perhaps an ORM would help mapping to domain objects while handling the business or updating multiple tables.