RickyFS,
Why not introduce a 3~5 hour time-out system on the captcha codes? If they login from 2~3 different IPs, then for the next 3~5 hour, the captcha will be activated for logins. If within that time, only 1 ip was used, captcha will be disabled. If they login with different IPs within the time limit, it'll keep extending the time-out upto 24 hour. I dont think your users would be complaining then.
You can implement it simply by adding 3 more rows to the user table, 1 for their loggin IP, 1 for loggin time, and last one for their time-out time. When a user logs in, their loggin ip and time is saved to database. When they loggin with a different ip, within 3~5 hours of last login time, update the database with new loggin IP and loggin time, and set timeout to 3~5 hours from current loggin time. If the timeout time is > current time, captcha will be active. Otherwise, no captcha.
This is just one way to do it. I am sure your devlopers will be able to come up with lots of other ways to implement a similar system. Please consider this option. This will be a perfect middle ground between where you are now and what the users wants.
Thanks in advance.