apt-get dependency issue Open-SSH Client

This is on an Ubuntu 12.04 Server.

I'm getting this error when trying to run any apt-get install (trying to install unrelated, arbitrary packages):

dpkg: dependency problems prevent configuration of openssh-server:
 openssh-server depends on openssh-client (= 1:5.9p1-5ubuntu1.1); however:
  Version of openssh-client on system is 1:5.9p1-5ubuntu1.4.
dpkg: error processing openssh-server (--configure):
 dependency problems - leaving unconfigured
No apport report written because the error message indicates its a followup error from a previous failure.
                                                                                                          dpkg: dependency probms prevent configuration of ssh:
 ssh depends on openssh-server; however:
  Package openssh-server is not configured yet.
dpkg: error processing ssh (--configure):
 dependency problems - leaving unconfigured
No apport report written because the error message indicates its a followup error from a previous failure.
                                                                                                          Errors were encounter while processing:
 openssh-server
 ssh
E: Sub-process /usr/bin/dpkg returned an error code (1)

Installing the client version in question leads to:

sudo apt-get install openssh-client=1:5.9p1-5ubuntu1.1
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Version '1:5.9p1-5ubuntu1.1' for 'openssh-client' was not found

Various attempts to fix it with lack of background knowledge failed, e.g.

dpkg-reconfigure -a
apt-get -f install

Can somebody give advice how to tackle the problem, possibly demanding more infos that are necessary from my side?

How can the openssh update (that I guess failed) be reverted or taken out of focus, so I am able to install other packages?

Edit:

Output of apt-cache policy openssh-client is:

openssh-client:
  Installed: 1:5.9p1-5ubuntu1.4
  Candidate: 1:5.9p1-5ubuntu1.4
  Version table:
 *** 1:5.9p1-5ubuntu1.4 0
        500 http://archive.ubuntu.com/ubuntu/ precise-updates/main amd64 Packages
        100 /var/lib/dpkg/status
     1:5.9p1-5ubuntu1.3 0
        500 http://security.ubuntu.com/ubuntu/ precise-security/main amd64 Packages
     1:5.9p1-5ubuntu1 0
        500 http://archive.ubuntu.com/ubuntu/ precise/main amd64 Packages

Just for completeness the /etc/apt/sources.list:

deb http://archive.ubuntu.com/ubuntu precise main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu precise-updates main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu precise-backports main restricted universe multiverse
deb http://security.ubuntu.com/ubuntu precise-security main restricted universe multiverse

Just remove these packages to let you use apt for other packages. Execute this commands in terminal.

sudo apt-get remove openssh-server openssh-client --purge && sudo apt-get autoremove && sudo apt-get autoclean && sudo apt-get update

Then reinstall openssh server and client .

sudo apt-get install openssh-server openssh-client