Create an asp web  page to submit contact  info. It can be hosted on a
different server, it doesn't really matter. Then, add  a page viewer
web part  to your sharepoint site and set the url to point to your
contact page. This should work.

Why not just direct people directly to the WSS generated New Contact page? Or,
if the actual data entry must be done as a Web Part on another page, use the
Page Viewer Web Part (or better yet the Web Capture Web Part) on the existing
page?

There are several ways that you can accomplish this. The least intrusive is to
add a link to the SharePoint generated new form  page.

It is possible to use the Page Viewer Web Part to put this form onto another
page but it will be clunky at best. If you are bent on this approach, check out
the Web Capture Web Part instead.

If I had to do this in a no code way, I would probably look at the Data Form Web
Part (assumes WSS v3). It can edit lists from pages other than the out of the
box list pages.