Dear dshahin,

when you say:
<cite>"This may seem trivial and/or insecure to some"</cite>
I have to say that there is no black or white or at least no clear border between them.
As you can't read cookies set by any other server you will need to connect to that other server and you will have to get the verification back - otherwise it would be sent to the client which seems useless for your approach.
Security is always the most important concern: so what will happen? You give the verification service provider support to keep track of the users behaviour - would you like to? Would your users like you to do so as well?
Even if the provider of such a service does not intend to use this kind of information - would you rely on his systems security and would you deny the risk of his system being hacked and all the information being stolen???

So better think about persistent cookies if you are just about to store user preferences such as colour schemes or display orders etc.
But if you wan't your users to trust you in the way they give you (personell) information you will have to implement and use SSL and encryption (such as strong as PGP) in the most effordable way by yourself.

Have a nice day
All decision is left to your taste