301 is Google's preferred method so if you really are doing a 301, no need ot change.
You could use Google's URL removal tool to remove your old URLS provided there is no page there, and it must show a 404 Page Not found.
Are you sure you are not accidentally doing a 302 instead? This is a common error. That would be DEADLY.
We had some redirects that we could have SWORN were 301s, but we discovered to our horror they were 302 redirects.
On some servers if you do not specify explicitly in the command line that you want a 301 redirect, your server gives you a 302 redirect. OOPS!
How do you test for sure? I like to use Seoconsultants server headers tool. To find it just search this in google with quotes:
"Check Server Headers Tool - HTTP Status Codes Checker"
All you do is enter the URL that you are redirecting into their header tool form online, and look at the output of the form, for the line that says "HTTP Status Code", and see if it says 301 or 302. If it says 302, then you have work to do.
Moral of the story, DO NOT ASSUME you have a 301 redirect unless it is explicitly called out in your command line.
I have always been a fan of abo#*$!e addressing over relative addressing for reasons like this. Never take chances.