C#/WPF: KeyBinding not triggering Command

I have declared <InputBindings>

<UserControl.InputBindings>
    <KeyBinding Key="C" Modifiers="Ctrl" Command="{Binding CopyImageCommand}" />
    <KeyBinding Key="V" Modifiers="Ctrl" Command="{Binding PasteImageCommand}" />
</UserControl.InputBindings>

For testing purposes, I have added buttons bound to those commands too

<Button Command="{Binding CopyImageCommand}" Content="Copy" />
<Button Command="{Binding PasteImageCommand}" Content="Paste" />

I noticed that when the paste button is enabled, when i press Ctrl-V nothing happens. Ctrl-C seems to work. For that, a list box item is selected, I am not sure if it makes any difference. Anyone knows why is my PasteImageCommand not triggering?

I am using .NET 4 btw

UPDATE

A fuller code snipplet

<UserControl x:Class="QuickImageUpload.Views.ShellView"
             xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
             xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
             xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
             xmlns:d="http://schemas.microsoft.com/expression/blend/2008" 
             xmlns:vm="clr-namespace:QuickImageUpload.ViewModels"
             mc:Ignorable="d" 
             d:DesignHeight="300" d:DesignWidth="300">
    <UserControl.InputBindings>
        <KeyBinding Key="C" Modifiers="Ctrl" Command="{Binding CopyImageCommand}" />
        <KeyBinding Key="V" Modifiers="Ctrl" Command="{Binding PasteImageCommand}" />
    </UserControl.InputBindings>
    <UserControl.DataContext>
        <vm:ShellViewModel />
    </UserControl.DataContext>
    <Grid>
        <Grid.RowDefinitions>
            <RowDefinition Height="50" />
            <RowDefinition Height="*" />

UPDATE

I found out I need to put the KeyBindings in the MainWindow, but the commands are in the ViewModel, how can i set key bindings in the ShellView which then binds to commands in the ShellViewModel?

Make sure that you are not having binding errors. You set the DataContext of the user control, but make sure that the commands can bind to it. Sometimes, WPF just uses the order of appearance, and the DataContext is set later then the commands.

Probably, the output window of VS already shows binding errors for the commands. Try putting the DataContext definition on top (and teach yourself to do this for all views).

To avoid hardcoded KeyBindings, I have derived Josh Smiths RelayCommand-Class and added Shortcut-related stuff:

class UIRelayCommand : RelayCommand, INotifyPropertyChanged
{
    private static Dictionary<ModifierKeys, string> modifierText = new Dictionary<ModifierKeys, string>()
    {
        {ModifierKeys.None,""},
        {ModifierKeys.Control,"Ctrl+"},
        {ModifierKeys.Control|ModifierKeys.Shift,"Ctrl+Shift+"},
        {ModifierKeys.Control|ModifierKeys.Alt,"Ctrl+Alt+"},
        {ModifierKeys.Control|ModifierKeys.Shift|ModifierKeys.Alt,"Ctrl+Shift+Alt+"},
        {ModifierKeys.Windows,"Win+"}
    };

    private Key _key;
    public Key Key
    {
        get { return _key; }
        set { _key = value; RaisePropertyChanged("Key"); RaisePropertyChanged("GestureText"); }
    }

    private ModifierKeys _modifiers;
    public ModifierKeys Modifiers
    {
        get { return _modifiers; }
        set { _modifiers = value; RaisePropertyChanged("Modifiers"); RaisePropertyChanged("GestureText");}
    }

    public string GestureText
    {
        get { return modifierText[_modifiers] + _key.ToString(); }
    }

    public UIRelayCommand(Action<object> execute, Predicate<object> canExecute, Key key, ModifierKeys modifiers)
        : base(execute, canExecute)
    {
        _key = key;
        _modifiers = modifiers;
    }


    public event PropertyChangedEventHandler PropertyChanged;

    public void RaisePropertyChanged(string name)
    {
        if (PropertyChanged != null)
            PropertyChanged(this, new PropertyChangedEventArgs(name));
    }
}

then create the command in the ViewModel:

private ICommand _newFileCommand;
public ICommand NewFileCommand
{
    get
    {
        if (_newFileCommand == null)
            _newFileCommand = new UIRelayCommand(p => OnNewFile(p), p => CanNewFile(p), Key.N, ModifierKeys.Control);
        return _newFileCommand;
    }
}
protected void OnNewFile(object p)
{
    //open file...
}
protected bool CanNewFile(object p)
{
    return true;
}

and bind it in the View:

<Window.InputBindings>
    <KeyBinding Command="{Binding NewFileCommand}" Key="{Binding NewFileCommand.Key}" Modifiers="{Binding NewFileCommand.Modifiers}"  />
</Window.InputBindings>
...
<MenuItem Header="New File" Command="{Binding NewFileCommand}" InputGestureText="{Binding NewFileCommand.GestureText}" />

With this approach I can allow the user to adjust the shortcuts at runtime (in my configuration-window)