Looks like you should store somewhere that RC4 hash, because both client and server should do the same actions on challenge bytes and than server should compare results.
- Saving plain text password - bad idea, forget about it.
- If you save it as PasswordMD4 in database - it not add security more then PC4 by self.
- Saving in other table - no different with previous variant.
- Spring security - don't know how it can be apply here.
You can store important or all DB data on encrypted partition, but it degrade performance a little.
I can suggest store RC4 password into SHA-1 field, but encrypted. 3DES will be enough, maybe with some salt. You already should have salt somewhere for your SHA-1 hash. When you need RC4 hash, simple decrypt value from DB, subtract (or XOR) salt and do usual authentication procedure.
And don't use NTLM v1, it is old and unsecure.