Are you now using a connection to that server that crosses over from one
internet provider's equipment to another's before it reaches the server?
If so, such connections to port 25 are likely to be blocked to cause trouble
for spammers, and you got blocked too.  In such a case, you need to ask
aarestad.com if their outgoing mail server allows such connections on any
port other than port 25, and if so, where to find any details on how to
switch over to the other port.  Just trying all the ports is a very slow way
to find out, since there are about 65,000 ports available and it is unlikely
that more than a few of them will accept outgoing mail.

Also, you may want to ask if they are up to date on the updates for
their server software.  Microsoft came out with an update for server
software several months ago that is needed to make the server work
well with Vista users.

Click on your Outbox and see if messages you tried to send have
stayed there more than a few minutes.  If so, move these messages
to the Drafts folder or delete them, then restart Windows Mail and
test the results by sending yourself a short message.

If any of the messages refuse to either move or delete, download and
install this hotfix, with Windows Mail not running:

http://support.microsoft.com/default.aspx/kb/941090

Although it's labelled as for mail stuck in the Outbox, it also works in
other folders.  If you don't know whether you have a 32-bit version
of Vista or a 64-bit version, try the hotfix for the 32-bit version
first.  Certain common antivirus programs, such as most of those
from Norton or McAfee, tend to cause stuck messages and other
problems in Windows Mail, although seldom immediately, so if you
have such a program, remember where to find the hotfix and hope
it will install again if you need it again.  A recent version of the Trend
antivirus program also causes assorted problems in Windows Mail.

The Vista SP1 update also includes this hotfix, so it's possible Vista
will refuse to let you install it again.

This hotfix doesn't always delete the troublesome messages, but should
at least make it possible for you to delete them.

Aarestad.com is not your ISP. As such, your real ISP will block any
attempt to use port 25 on an external server like mail.aarestad.com.
For the reason why this is done, see
http://www.postcastserver.com/help/Port_25_Blocking.aspx
I'm surprised your ISP's tech support played dumb (well, not *too*
surprised).

The easiest workaround is to replace that SMTP server with
the name of your ISP's SMTP server. If you are sending from a
laptop while away from home, you will need a different workaround.