apt-get doesn't work behind a proxy

My company uses an HTTP proxy and our various Ubuntu 12.04 servers therefore need to be configured properly, namely by setting \etc\apt\apt.conf.d\80proxy to:

Acquire::http::Proxy "http://proxy.mycompany.com:80";

Acquire::http::No-Cache true;

Now, since a few days, this method suddenly stopped working: I run into sum mismatch errors. I have tried all the usual tricks found on stackoverflow or on the web, among others:

sudo rm -fR /var/lib/apt/lists/*

sudo apt-get clean

But nothing seems to work. I even switched to a FTP server, without any luck. What's a radical solution to this problem? Is it likely that the proxy server has some kind of issue? What could it be?

Using Ubuntu 12.04

I've found that the following works for me, as far as using apt from the terminal alone is concerned:

Leave /etc/apt/apt.conf empty, so that apt falls back on the $*_proxy environment variables.
Make sure your environment variables are properly set: For example, you could add in .bashrc:
```
http_proxy="http://username:password@proxyserver:port"
# And so on for other proxy settings like https_proxy and ftp_proxy
```
If your username or password contains any special characters, they may need to be URL encoded.
Make sudo use your environment variables and not its own. This is done by editing the /etc/sudoers file. Be careful while doing this! Use only the sudo visudo command to edit the file; any errors may leave you unable to re-enter sudo mode! Add the following:
```
Defaults env_keep+="http_proxy https_proxy ftp_proxy socks_proxy"
```
This ensures that sudo retains these variables when executing sudo apt-get install ... etc.

I found this out from Ubuntu's apt-get howto.

Do let me know if it works :)

To use apt-get through a proxy, I do the following - you do need to be able to access the internet (e.g. through a browser like Firefox) though:

sudo apt-get --print-uris install PROGRAM

This prints the urls (and other info like md5sums) of the packages needed to carry out the installation, so you can download them. For example, using supertux:

wilf@comp:~$ sudo apt-get install --print-uris supertux
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following extra packages will be installed:
  supertux-data
The following NEW packages will be installed
  supertux supertux-data
0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
Need to get 59.4 MB of archives.
After this operation, 80.0 MB of additional disk space will be used.
Do you want to continue [Y/n]? Y
'http://gb.archive.ubuntu.com/ubuntu/pool/universe/s/supertux/supertux-data_0.3.3-6_all.deb' supertux-data_0.3.3-6_all.deb 58590640 MD5Sum:68bd36f2c262f7caed1b5c947977202a
'http://gb.archive.ubuntu.com/ubuntu/pool/universe/s/supertux/supertux_0.3.3-6_i386.deb' supertux_0.3.3-6_i386.deb 804782 MD5Sum:a49c6c3c918bae2c968b3da6ac725b06

Then download the .deb files from the given links (preferably into a empty folder), through a browser that works through the proxy etc, and you can then install them using Software Centre; or using cd /FOLDER/WITH/DOWNLOADED-DEB-FILES and one of these commands in terminal