I'm not sure where you are seeing a "deploy" menu  in vs2005. It's not
there in regular 2005 nor in a webpart  generated from Visual Studio
Extensions for WSS. But here are some things that may help.

1. Make sure the web part is in either the bin of the webapp or
the GAC. Yours seems to be in the GAC.

2. Make sure you have a SafeControl entry for the webpart in the
Web.Config.

3. Add either a .DWP or .WEBPART file  for the webpart to the
SiteCollection Webpart gallery or the server gallery(the WPCATALOG
directory of the Web Application).

4. Make sure that vs2005  can see the .pdb file associated with the
.dll. an easy way to do this if the .dll is in the GAC would be to use
Tools>Options>Debbugging>Symbols and add the location of the .pdb file.
For the bin directory it should be deployed  with the .dll if you are
setting the build  path to \bin.

5. Make sure your build is set  to Debug and not release.

6. Attach to the W3WP.exe processes using the Debug>Attach to
process menu. If you are not physically on the server make sure you
attach to the W3WP processes on the server.

7. Set a break  point in your code  and browse to the website and
load the webpart.

To remove  an existing .dll from the GAC. Open C:\windows\assembly, find
the webpart, right click  on it and pick uninstall.