Index: src/OFDNSResolver.m
==================================================================
--- src/OFDNSResolver.m
+++ src/OFDNSResolver.m
@@ -983,10 +983,13 @@
 			  authorityRecords: authorityRecords
 			 additionalRecords: additionalRecords];
 	} @catch (id e) {
 		exception = e;
 	}
+
+	if (exception != nil)
+		response = nil;
 
 	if ([context->_delegate respondsToSelector:
 	    @selector(resolver:didPerformQuery:response:exception:)])
 		[context->_delegate resolver: self
 			     didPerformQuery: context->_query

Index: src/OFHostAddressResolver.h
==================================================================
--- src/OFHostAddressResolver.h
+++ src/OFHostAddressResolver.h
@@ -35,10 +35,12 @@
 	of_socket_address_family_t _addressFamily;
 	OFDNSResolver *_resolver;
 	OFDNSResolverSettings *_settings;
 	of_run_loop_mode_t _Nullable _runLoopMode;
 	id <OFDNSResolverHostDelegate> _Nullable _delegate;
+	bool _isFQDN;
+	size_t _searchDomainIndex;
 	unsigned int _numExpectedResponses;
 	OFMutableData *_addresses;
 }
 
 - (instancetype)initWithHost: (OFString *)host

Index: src/OFHostAddressResolver.m
==================================================================
--- src/OFHostAddressResolver.m
+++ src/OFHostAddressResolver.m
@@ -16,19 +16,21 @@
  */
 
 #include "config.h"
 
 #import "OFHostAddressResolver.h"
+#import "OFArray.h"
 #import "OFDNSResolver.h"
 #import "OFDNSResolverSettings.h"
 #import "OFData.h"
 #import "OFDate.h"
 #import "OFDictionary.h"
 #import "OFRunLoop.h"
 #import "OFString.h"
 #import "OFTimer.h"
 
+#import "OFDNSQueryFailedException.h"
 #import "OFInvalidArgumentException.h"
 #import "OFInvalidFormatException.h"
 #import "OFResolveHostFailedException.h"
 
 @interface OFHostAddressResolverDelegate: OFObject <OFDNSResolverHostDelegate>
@@ -40,10 +42,31 @@
 }
 @end
 
 static const of_run_loop_mode_t resolveRunLoopMode =
     @"of_host_address_resolver_resolve_mode";
+
+static bool
+isFQDN(OFString *host, unsigned int minNumberOfDotsInAbsoluteName)
+{
+	const char *UTF8String;
+	size_t length;
+	unsigned int dots;
+
+	if ([host hasSuffix: @"."])
+		return true;
+
+	UTF8String = host.UTF8String;
+	length = host.UTF8StringLength;
+	dots = 0;
+
+	for (size_t i = 0; i < length; i++)
+		if (UTF8String[i] == '.')
+			dots++;
+
+	return (dots >= minNumberOfDotsInAbsoluteName);
+}
 
 static bool
 addressForRecord(OF_KINDOF(OFDNSResourceRecord *) record,
     const of_socket_address_t **address,
     of_socket_address_family_t addressFamily)
@@ -125,25 +148,64 @@
 	[_delegate release];
 	[_addresses release];
 
 	[super dealloc];
 }
+
+- (void)sendQueries
+{
+	OFString *domainName;
+
+	if (!_isFQDN) {
+		OFString *searchDomain = [_settings->_searchDomains
+		    objectAtIndex: _searchDomainIndex];
+
+		domainName = [OFString stringWithFormat: @"%@.%@",
+							 _host, searchDomain];
+	} else
+		domainName = _host;
+
+#ifdef OF_HAVE_IPV6
+	if (_addressFamily == OF_SOCKET_ADDRESS_FAMILY_IPV6 ||
+	    _addressFamily == OF_SOCKET_ADDRESS_FAMILY_ANY) {
+		OFDNSQuery *query = [OFDNSQuery
+		    queryWithDomainName: domainName
+			       DNSClass: OF_DNS_CLASS_IN
+			     recordType: OF_DNS_RESOURCE_RECORD_TYPE_AAAA];
+		_numExpectedResponses++;
+		[_resolver asyncPerformQuery: query
+				 runLoopMode: _runLoopMode
+				    delegate: self];
+	}
+#endif
+
+	if (_addressFamily == OF_SOCKET_ADDRESS_FAMILY_IPV4 ||
+	    _addressFamily == OF_SOCKET_ADDRESS_FAMILY_ANY) {
+		OFDNSQuery *query = [OFDNSQuery
+		    queryWithDomainName: domainName
+			       DNSClass: OF_DNS_CLASS_IN
+			     recordType: OF_DNS_RESOURCE_RECORD_TYPE_A];
+		_numExpectedResponses++;
+		[_resolver asyncPerformQuery: query
+				 runLoopMode: _runLoopMode
+				    delegate: self];
+	}
+}
 
 -  (void)resolver: (OFDNSResolver *)resolver
   didPerformQuery: (OFDNSQuery *)query
 	 response: (OFDNSResponse *)response
 	exception: (id)exception
 {
 	_numExpectedResponses--;
 
-	if (exception != nil && _numExpectedResponses == 0) {
-		if ([_delegate respondsToSelector:
-		    @selector(resolver:didResolveHost:addresses:exception:)])
-			[_delegate resolver: _resolver
-			     didResolveHost: _host
-				  addresses: nil
-				  exception: exception];
+	if ([exception isKindOfClass: [OFDNSQueryFailedException class]] &&
+	    [exception error] == OF_DNS_RESOLVER_ERROR_SERVER_NAME_ERROR &&
+	    !_isFQDN && _numExpectedResponses == 0 && _addresses.count == 0 &&
+	    _searchDomainIndex + 1 < _settings->_searchDomains.count) {
+		_searchDomainIndex++;
+		[self sendQueries];
 		return;
 	}
 
 	for (OF_KINDOF(OFDNSResourceRecord *) record in
 	    [response.answerRecords objectForKey: query.domainName]) {
@@ -178,45 +240,12 @@
 
 	if ([_delegate respondsToSelector:
 	    @selector(resolver:didResolveHost:addresses:exception:)])
 		[_delegate resolver: _resolver
 		     didResolveHost: _host
-			  addresses: _addresses
-			  exception: exception];
-}
-
-- (void)sendQueries
-{
-	/* FIXME: Add seach domain */
-	OFString *domainName = _host;
-	OFDNSQuery *query;
-
-#ifdef OF_HAVE_IPV6
-	if (_addressFamily == OF_SOCKET_ADDRESS_FAMILY_IPV6 ||
-	    _addressFamily == OF_SOCKET_ADDRESS_FAMILY_ANY) {
-		query = [OFDNSQuery
-		    queryWithDomainName: domainName
-			       DNSClass: OF_DNS_CLASS_IN
-			     recordType: OF_DNS_RESOURCE_RECORD_TYPE_AAAA];
-		_numExpectedResponses++;
-		[_resolver asyncPerformQuery: query
-				 runLoopMode: _runLoopMode
-				    delegate: self];
-	}
-#endif
-
-	if (_addressFamily == OF_SOCKET_ADDRESS_FAMILY_IPV4 ||
-	    _addressFamily == OF_SOCKET_ADDRESS_FAMILY_ANY) {
-		query = [OFDNSQuery
-		    queryWithDomainName: domainName
-			       DNSClass: OF_DNS_CLASS_IN
-			     recordType: OF_DNS_RESOURCE_RECORD_TYPE_A];
-		_numExpectedResponses++;
-		[_resolver asyncPerformQuery: query
-				 runLoopMode: _runLoopMode
-				    delegate: self];
-	}
+			  addresses: (_addresses.count > 0 ? _addresses : nil)
+			  exception: (_addresses.count == 0 ? exception : nil)];
 }
 
 - (void)asyncResolve
 {
 	void *pool = objc_autoreleasePoolPush();
@@ -280,10 +309,11 @@
 
 		objc_autoreleasePoolPop(pool);
 		return;
 	}
 
+	_isFQDN = isFQDN(_host, _settings->_minNumberOfDotsInAbsoluteName);
 	_addresses = [[OFMutableData alloc]
 	    initWithItemSize: sizeof(of_socket_address_t)];
 
 	[self sendQueries];