Rahul, I am working on a similar problem right now. Having read a number of the Excel forums and the MS help boards on this issue, I can tell you that it's really TWO problems:
A) a standard copy-paste in Excel copies the validations from the source to the destination. If you don't have any safeguards, this wipes out the validation from your special column when a user pastes into it. B) Excel only performs validation on single cells and not on paste actions. Pretty weak.
I can solve problem A for you; I think you will need VBA to do custom validation for problem B. See the links at the bottom of this post for some ideas; I'm not a pro at VBA so I can't really say which will work for you.
For problem A: go to the Review tab and turn Protection on at either the sheet or workbook level :) I haven't seen anyone else mention this solution, but it works really well. When protection is turned on, the user cannot overwrite the validations in your column with a paste.
The default rights for a user in a protected sheet are pretty minimal. If your users need a lot of rights, like the ability to delete rows, just enable the rights they need in the Protect dialog by checking the checkboxes. I have everything enabled except Insert Hyperlinks and I still can't overwrite validation when protection is turned on.
Here are some relevant links for you:
http://www.mrexcel.com/forum/excel-questions/64596-data-validation-why-does-not-work-when-pasting-values.html
http://spreadsheetpage.com/index.php/tip/ensuring_that_data_validation_is_not_deleted/
https://social.msdn.microsoft.com/Forums/office/en-US/961e3921-5fd2-430e-bf50-aecb75a4fe05/excel-cell-data-validations-fails-on-copypaste
http://www.mrexcel.com/forum/excel-questions/519807-pasting-into-cell-data-validation.html