You shouldn't have any problem with this. I used to have a program like this running on my site (verify user emails after they sign up). Worked fine, as long as you don't send out massive amount of emails.
What you are wanting to do is an integral part of many popular pieces of software such as vBulletin, IPB, phpBB3, SMF, MyBB, etc... I don't think that any quality and reputable provider is going to suspend you for verifying submitted email addresses as long as the users are actually entering their own email addresses and understand that they will be emailed to verify the address.
If you get a large amount of spam complaints you will have problems at just about any host.