Dear Cilli,

thanks for your help so far. Just before I hit submit reply, I thought we finally have some progress. But now I am editing the post, as unfortunately wifi stopped working again.
Here is what I have written before and I will add a small update at the end:

I did remove the rt2860sta module as you have suggested. I did couple of reboots and removed any reference to rt28060sta I could find (via locate).

WiFi still did not work, although connected.

So I went inside my router and disabled wifi security - voila, wifi has been running now for about 20 minutes.

Here's an output of iwconfig now (Invalid misc is now down to 3, whatever it is )
lo        no wireless extensions.

wlan0     IEEE 802.11bgn  ESSID:"MI6"  
          Mode:Managed  Frequency:2.412 GHz  Access Point: CC:5D:4E:B4:05:C8   
          Bit Rate=135 Mb/s   Tx-Power=20 dBm   
          Retry  long limit:7   RTS thr:off   Fragment thr:off
          Power Management:off
          Link Quality=58/70  Signal level=-52 dBm  
          Rx invalid nwid:0  Rx invalid crypt:0  Rx invalid frag:0
          Tx excessive retries:0  Invalid misc:3   Missed beacon:0

eth0      no wireless extensions.
and here is output of sudo modinfo rt2800pci
filename:       /lib/modules/3.2.0-35-generic/kernel/drivers/net/wireless/rt2x00/rt2800pci.ko
license:        GPL
firmware:       rt2860.bin
description:    Ralink RT2800 PCI & PCMCIA Wireless LAN driver.
version:        2.3.0
srcversion:     B814F1B7538F8B99ECC7D4E
alias:          pci:v00001814d0000539Fsv*sd*bc*sc*i*
alias:          pci:v00001814d0000539Asv*sd*bc*sc*i*
alias:          pci:v00001814d00005390sv*sd*bc*sc*i*
alias:          pci:v00001814d00003593sv*sd*bc*sc*i*
alias:          pci:v00001814d00003592sv*sd*bc*sc*i*
alias:          pci:v00001814d00003562sv*sd*bc*sc*i*
alias:          pci:v00001814d00003062sv*sd*bc*sc*i*
alias:          pci:v00001814d00003060sv*sd*bc*sc*i*
alias:          pci:v00001432d00007722sv*sd*bc*sc*i*
alias:          pci:v00001432d00007711sv*sd*bc*sc*i*
alias:          pci:v00001814d00003390sv*sd*bc*sc*i*
alias:          pci:v00001A3Bd00001059sv*sd*bc*sc*i*
alias:          pci:v00001462d0000891Asv*sd*bc*sc*i*
alias:          pci:v00001432d00007768sv*sd*bc*sc*i*
alias:          pci:v00001432d00007758sv*sd*bc*sc*i*
alias:          pci:v00001432d00007748sv*sd*bc*sc*i*
alias:          pci:v00001432d00007738sv*sd*bc*sc*i*
alias:          pci:v00001432d00007728sv*sd*bc*sc*i*
alias:          pci:v00001432d00007727sv*sd*bc*sc*i*
alias:          pci:v00001432d00007708sv*sd*bc*sc*i*
alias:          pci:v00001814d00003092sv*sd*bc*sc*i*
alias:          pci:v00001814d00003091sv*sd*bc*sc*i*
alias:          pci:v00001814d00003090sv*sd*bc*sc*i*
alias:          pci:v00001814d00000781sv*sd*bc*sc*i*
alias:          pci:v00001814d00000701sv*sd*bc*sc*i*
alias:          pci:v00001814d00000681sv*sd*bc*sc*i*
alias:          pci:v00001814d00000601sv*sd*bc*sc*i*
depends:        rt2x00lib,rt2800lib,rt2x00pci,eeprom_93cx6
intree:         Y
vermagic:       3.2.0-35-generic SMP mod_unload modversions 686 
parm:           nohwcrypt:Disable hardware encryption. (bool)
I would like to use WPA2/AES. Before I do any changes, I will wait for any suggestions you may have.

After wifi stopped working:
While I was writing the post, I noticed that I have ping running in the terminal, constantly pinging the gateway. I stopped it to get output of the commands above. By the time I finished the post, the problem reappeared (retrying ping did not help, as I cannot ping gateway anymore).
Just for your info, on the same laptop I can boot also into Win XP. There, I have no problem with the wifi - this is just to rule out the hw or router problem.

Thanks again.