Hmmm... the article I linked to above works somewhat. It lest you browse the domains in the Network Neighborhood but they don’t show as a login domain.
Establishing a connection between both domains and putting in place a trust between them is sadly not an option.
Thats a nice contradiction 
You HAVE to establish a trust in order to be able to show that domain as logon domain. There is no other way.
It will cost nothing (Or not much). All 2003 AD's support trusts. The VPN connection can be set by "Routing and Remote Access" or by the better kind of ADSL/Cable modem routers (a decent priced good quality router like Draytek)
Besides even if you achieve this, loggin in will likely go pretty slow. Loading profiles over internet and that sort of stuff. It does work fine however, we've got a couple of companies with this setup. However I recommend using Terminal Services since that is easier to setup and works fastest. Then again best practise is to have a 2nd server with Terminal Services and not letting ppl use Terminal Services on the Primary Domain Controller. You could however still setup TS on the PDC but you'd have some strict policy work to do then. Hiding drives etc. Also, since you said they we're small offices if they have 2003 Small Business edition it is not possible to have more then 2 clients on TS at the same time. MS limited this on purpose. You'd have to get 2003 Standard as a TS server according to MS, this is recommended as best practise as well.
Anyway enough of my ramblings, hope you'll find some usefull info in there somewhere....
