update-alternatives: error: /var/lib/dpkg/alternatives/vim corrupt: invalid status

Whenever I try to install, update, or do anything with apt-get, I always get a error message similar to this, griping about vim:

0 upgraded, 0 newly installed, 0 to remove and 2 not upgraded.
1 not fully installed or removed.
After this operation, 0 B of additional disk space will be used.
Do you want to continue [Y/n]? y
Setting up vim (2:7.3.154+hg~74503f6ee649-2ubuntu3.1) ...
update-alternatives: error: /var/lib/dpkg/alternatives/vim corrupt: invalid status
dpkg: error processing vim (--configure):
 subprocess installed post-installation script returned error exit status 2
Errors were encountered while processing:
 vim

Not exactly sure what's going on here. My assumption is that something is corrupt with vim? Here is what I've tried to fix the issue:

1. Uninstall vim (sudo apt-get remove vim) - Removing fails and gives back an error similar to the one above.
2. sudo apt-get purge vim - Fails, same errors.

3. Removing the /var/lib/dpkg/alternatives/vim file mentioned in the error message and then trying remove/purge again - Removing/purging still fails, but instead of:

   update-alternatives: error: /var/lib/dpkg/alternatives/vim corrupt: invalid status
   

   In its place, I get:

   update-alternatives: error: /var/lib/dpkg/alternatives/vimdiff corrupt: line not terminated while trying to read status
   

4. Installing vim again - Fails, same errors.

5. sudo apt-get clean && sudo apt-get autoremove- Fails, same errors.
6. sudo apt-get install --fix-broken - Fails, same errors.

This is getting a bit annoying. vim just won't die. What's going wrong? What am I doing wrong? How do I fix this?

Help would be greatly appreciated.

** EDIT **

As requested:

Output of LC_MESSAGES=C update-alternatives --query vim:

Link: vim
Status: auto
Best: /usr/bin/vim.basic
Value: /usr/bin/vim.basic

Alternative: /usr/bin/vim.basic
Priority: 30

content of /var/lib/dpkg/alternatives/vimdiff:

b0VIM 7.3Ýroot

Can't fetch the content of /var/lib/dpkg/alternatives/vim because I deleted it, haha sorry.

Solution 1:

The alternatives entries are hopelessly broken.

1. You should remove them with:

   sudo update-alternatives --remove-all vim
   sudo rm -f /etc/alternatives/vim /var/lib/dpkg/alternatives/vim
   

   If update-alternatives complains about corrupt files again, ignore it and just proceed to delete them with the next command.

2. Then re-install their packages with:

   sudo apt-get install --reinstall vim
   

   This will restore the alternatives entries according to the packages available on your system.

3. Proceed analogously for vimdiff, rvim and other corrupted entries.