How to enhance login/password weak authentication ?

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

I manage a social website with a large number of subscribers. We have a
regular login/password authentication for our subscribers. Recently we
had a problem - because of phishing or keylogger or breakin ( nobody
knows exactly) many accounts of the web site were hijacked. Someone
wrote a program (bot) that sent spam using private messages on our site
through hijacked accounts. We changed the passwords meantime and put
some captcha forms, but now we seek for a permanent solution to solve
this problem. We need stronger authentication than login/password.

 I looked at hardware based authentication like RSAsecurity tokens, but
it is not acceptable for us because it is very expensive and we have
multinational user base. I also looked at software based solutions like
Bharosa, that is most suitable for us, but they mostly target finance
institutions and they are expensive.

 Please, share your experience with a solution you use to prevent
account hijacking and bot logins, that enhance existing login/password
authenticatoin . Is there any scalable, easy to integrate, pay as you
grow authentication solution for consumer web sites? Thanks for any

Site Timeline