There is a couple of things you should try:
- I'm not sure with VPN but are your ports open 389 or 636 in firestarter. Try scanning localhost over the network tools.
- Can you reach the LDAP service with an other tool from your Linux box? Example with LAT
- In evolution settings I had to set the search scope to SUB
- In evolution you will only see entries if you write something to the search, you won't see all your entries if search is empty
- have you tried with the terminal commands:
ldapsearch -LLL -x -b 'ou=addressbook,dc=subdomain,dc=dyndns,dc=org' -H ldap://subdomain.dyndns.org -D 'uid=you,ou=users,dc=subdomain,dc=dyndns,dc=org' -W