I experienced the same problems as you, though I did not try
SingleSingonPermission etc. Even after adding my web  part to the SafeControls
list in the Web.config file. I was consistently getting the same error  that you
mention. Then I stumbled upon an article  that advised me to add it to the Web
Part gallery.

Now that I think of it, there could be an another possible reason, Is your
application name different from the namespace used in your application. if so
in the Safe controls list you should add namespace.assemblyname as mentioned
below
<SafeControl Assembly="<Namespace>.<AssemblyName>", Version=x.x.x.x,
Culture=neutral,PublicKeyInfo=.xxxxxxxx Namespace=<Namespace> TypeName="*"
Safe="True" />

also you need to make the change in your DWP file.....

hope this solves this problem.

my opinion is, whether your webpart  is using SSP or not should not impact
deployment of the web part  because, it is only verified if the web part is a
safe control  while adding it to the site.