It was a problem with the synchronization of different servers. Maharepa has been added very recently and the ws server was not yet updated with the new entry.
I then conducted a secondary search on the GeoNames website at URL http://www.geonames.org/postal-codes/ and the following postal codes were returned with their Latitude and Longitude Reference.
Here is the list of Postal Codes i tested for Portugal
This is different issue. The granularity for Portugal of our geocoding is not as detailed as the number of postal codes. A lot of postal codes share the same coordinate estimation. The code you are using for the findnearby is just not included in the first rows returned of codes which share the same lat/lng estimate.
I cannot comment on the other countries as I have not enough information on the type of issue you see.