I just found this same problem this morning, and resolved it :)
The XsltListViewWebPart has a bug in it. The default XSL for the 'Edit' field calls a template called IfHasRight, which is defined in LAYOUTS\XSL\fldtypes.xsl. The comments on that template point out that it's actually checking for permission 2, ADD items. I wrote my own to check for 4, EDIT items.
You if you use SP Designer to customize your view, put your cursor in the 'edit icon' column and find the 'customize XSLT' command in the ribbon. Click 'customize item.' Then find the < Xsl> tag in your webpart's markup and replace the contents with the stylesheet below (or, put the stylesheet in an .xsl file and put the file's URL in the webpart's < XslLink> element.)
We're just doing two things: first, defining a new template called IfHasRight4 that checks the last digit of the permissions mask for any of the permissions containing EDIT; second, calling that template for the Edit column, instead of the default IfHasRight.
<xsl:stylesheet xmlns:x="http://www.w3.org/2001/XMLSchema" xmlns:d="http://schemas.microsoft.com/sharepoint/dsp" version="1.0" exclude-result-prefixes="xsl msxsl ddwrt" xmlns:ddwrt="http://schemas.microsoft.com/WebParts/v2/DataView/runtime" xmlns:asp="http://schemas.microsoft.com/ASPNET/20" xmlns:__designer="http://schemas.microsoft.com/WebParts/v2/DataView/designer" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:msxsl="urn:schemas-microsoft-com:xslt" xmlns:SharePoint="Microsoft.SharePoint.WebControls" xmlns:ddwrt2="urn:frontpage:internal" xmlns:o="urn:schemas-microsoft-com:office:office">
<xsl:include href="/_layouts/xsl/main.xsl"/>
<xsl:include href="/_layouts/xsl/internal.xsl"/>
<xsl:param name="AllRows" select="/dsQueryResponse/Rows/Row[$EntityName = '' or (position() >= $FirstRow and position() <= $LastRow)]"/>
<xsl:param name="dvt_apos">'</xsl:param>
<!-- ifhasrigth(4)-->
<xsl:template name="IfHasRight4" ddwrt:ghost="always">
<xsl:param name="thisNode" select="."/>
<xsl:variable name="mask" select="$thisNode/@PermMask"/>
<xsl:variable name="bit" select="substring($mask, string-length($mask))"/>
<xsl:choose>
<xsl:when test="$bit = '4' or $bit = '5' or $bit = '6' or $bit = '7' or
$bit = 'C' or $bit = 'c' or $bit = 'D' or $bit = 'd' or $bit = 'E' or $bit = 'e' or $bit = 'F' or $bit = 'f'">1</xsl:when>
<xsl:otherwise>0</xsl:otherwise>
</xsl:choose>
</xsl:template>
<xsl:template name="FieldRef_printTableCell_EcbAllowed.Edit" match="FieldRef[@Name='Edit']" mode="printTableCellEcbAllowed" ddwrt:dvt_mode="body" ddwrt:ghost="" xmlns:ddwrt2="urn:frontpage:internal">
<xsl:param name="thisNode" select="."/>
<xsl:param name="class" />
<td>
<xsl:if test="@ClassInfo='Menu' or @ListItemMenu='TRUE'">
<xsl:attribute name="height">100%</xsl:attribute>
<xsl:attribute name="onmouseover">OnChildItem(this)</xsl:attribute>
</xsl:if>
<xsl:attribute name="class">
<xsl:call-template name="getTDClassValue">
<xsl:with-param name="class" select="$class" />
<xsl:with-param name="Type" select="@Type"/>
<xsl:with-param name="ClassInfo" select="@ClassInfo"/>
</xsl:call-template>
</xsl:attribute>
<xsl:apply-templates select="." mode="PrintFieldWithECB">
<xsl:with-param name="thisNode" select="$thisNode"/>
</xsl:apply-templates>
</td>
</xsl:template>
<xsl:template name="FieldRef_Edit_body.Edit" ddwrt:dvt_mode="body" match ="FieldRef[(@Name='Edit') and @Name='Edit']" mode="Computed_body" ddwrt:ghost="" xmlns:ddwrt2="urn:frontpage:internal">
<xsl:param name="thisNode" select="."/>
<xsl:variable name="ID">
<xsl:call-template name="ResolveId"><xsl:with-param name="thisNode" select ="$thisNode"/></xsl:call-template>
</xsl:variable>
<xsl:variable name="hasRight">
<xsl:call-template name="IfHasRight4">
<xsl:with-param name="thisNode" select ="$thisNode"/>
</xsl:call-template>
</xsl:variable>
<xsl:variable name="requiresCheckout">
<xsl:call-template name="EditRequiresCheckout">
<xsl:with-param name="thisNode" select ="$thisNode"/>
</xsl:call-template>
</xsl:variable>
<xsl:choose>
<xsl:when test="$hasRight = '1'">
<a href="{$FORM_EDIT}&ID={$ID}" onclick="EditItemWithCheckoutAlert(event, '{$FORM_EDIT}&ID={$ID}', '{$requiresCheckout}', '{$thisNode/@IsCheckedoutToLocal}', '{$thisNode/@FileRef.urlencode}', '{$HttpVDir}', '{$thisNode/@CheckedOutUserId}', '{$Userid}');return false;" target="_self">
<img border="0" alt="{$thisNode/../@Edit}" src="/_layouts/images/edititem.gif"/>
</a>
</xsl:when>
<xsl:otherwise>
<xsl:text disable-output-escaping="yes" ddwrt:nbsp-preserve="yes">&nbsp;</xsl:text>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
<xsl:template name="View_Default_RootTemplate" mode="RootTemplate" match="View" ddwrt:dvt_mode="root" ddwrt:ghost="" xmlns:ddwrt2="urn:frontpage:internal">
<xsl:param name="ShowSelectAllCheckbox" select="'True'"/>
<xsl:if test="($IsGhosted = '0' and $MasterVersion=3 and Toolbar[@Type='Standard']) or $ShowAlways">
<xsl:call-template name="ListViewToolbar"/>
</xsl:if>
<table width="100%" cellspacing="0" cellpadding="0" border="0">
<xsl:if test="not($NoCTX)">
<xsl:call-template name="CTXGeneration"/>
</xsl:if>
<xsl:if test="List/@TemplateType=109">
<xsl:call-template name="PicLibScriptGeneration"/>
</xsl:if>
<tr>
<td>
<xsl:if test="not($NoAJAX)">
<iframe src="javascript:false;" id="FilterIframe{$ViewCounter}" name="FilterIframe{$ViewCounter}" style="display:none" height="0" width="0" FilterLink="{$FilterLink}"></iframe>
</xsl:if>
<table summary="{List/@title} {List/@description}" o:WebQuerySourceHref="{$HttpPath}&XMLDATA=1&RowLimit=0&View={$View}"
width="100%" border="0" cellspacing="0" dir="{List/@Direction}">
<xsl:if test="not($NoCTX)">
<xsl:attribute name="onmouseover">EnsureSelectionHandler(event,this,<xsl:value-of select ="$ViewCounter"/>)</xsl:attribute>
</xsl:if>
<xsl:if test="$NoAJAX">
<xsl:attribute name="FilterLink">
<xsl:value-of select="$FilterLink"/>
</xsl:attribute>
</xsl:if>
<xsl:attribute name="cellpadding">
<xsl:choose>
<xsl:when test="ViewStyle/@ID='15' or ViewStyle/@ID='16'">0</xsl:when>
<xsl:otherwise>1</xsl:otherwise>
</xsl:choose>
</xsl:attribute>
<xsl:attribute name="id">
<xsl:choose>
<xsl:when test="$IsDocLib or dvt_RowCount = 0">onetidDoclibViewTbl0</xsl:when>
<xsl:otherwise>
<xsl:value-of select="concat($List, '-', $View)"/>
</xsl:otherwise>
</xsl:choose>
</xsl:attribute>
<xsl:attribute name="class">
<xsl:choose>
<xsl:when test="ViewStyle/@ID='0' or ViewStyle/@ID='17'"><xsl:value-of select="$ViewClassName"/> ms-basictable</xsl:when>
<xsl:otherwise><xsl:value-of select="$ViewClassName"/></xsl:otherwise>
</xsl:choose>
</xsl:attribute>
<xsl:if test="$InlineEdit">
<xsl:attribute name="inlineedit">javascript: <xsl:value-of select="ddwrt:GenFireServerEvent('__cancel;dvt_form_key={@ID}')"/>;CoreInvoke('ExpGroupOnPageLoad', 'true');</xsl:attribute>
</xsl:if>
<xsl:apply-templates select="." mode="full">
<xsl:with-param name="ShowSelectAllCheckbox" select="$ShowSelectAllCheckbox"/>
</xsl:apply-templates>
</table>
<xsl:choose>
<xsl:when test="$IsDocLib or dvt_RowCount = 0"><script type='text/javascript'>HideListViewRows("onetidDoclibViewTbl0");</script></xsl:when>
<xsl:otherwise>
<script type='text/javascript'><xsl:value-of select ="concat('HideListViewRows("', $List, '-', $View, '");')"/></script>
</xsl:otherwise>
</xsl:choose>
</td>
</tr>
<xsl:if test="$dvt_RowCount = 0 and not (@BaseViewID='3' and List/@TemplateType='102')">
<tr>
<td>
<table width="100%" border="0" dir="{List/@Direction}">
<xsl:call-template name="EmptyTemplate" />
</table>
</td>
</tr>
</xsl:if>
</table>
<xsl:call-template name="pagingButtons" />
<xsl:if test="Toolbar[@Type='Freeform'] or ($MasterVersion=4 and Toolbar[@Type='Standard'])">
<xsl:call-template name="Freeform">
<xsl:with-param name="AddNewText">
<xsl:choose>
<xsl:when test="List/@TemplateType='104'">
<xsl:value-of select="'Add new announcement'"/>
</xsl:when>
<xsl:when test="List/@TemplateType='101' or List/@TemplateType='115'">
<xsl:value-of select="'Add document'"/>
</xsl:when>
<xsl:when test="List/@TemplateType='103'">
<xsl:value-of select="'Add new link'"/>
</xsl:when>
<xsl:when test="List/@TemplateType='106'">
<xsl:value-of select="'Add new event'"/>
</xsl:when>
<xsl:when test="List/@TemplateType='119'">
<xsl:value-of select="'Add new page'"/>
</xsl:when>
<xsl:otherwise>
<xsl:value-of select="'Add new item'"/>
</xsl:otherwise>
</xsl:choose>
</xsl:with-param>
<xsl:with-param name="ID">
<xsl:choose>
<xsl:when test="List/@TemplateType='104'">idHomePageNewAnnouncement</xsl:when>
<xsl:when test="List/@TemplateType='101'">idHomePageNewDocument</xsl:when>
<xsl:when test="List/@TemplateType='103'">idHomePageNewLink</xsl:when>
<xsl:when test="List/@TemplateType='106'">idHomePageNewEvent</xsl:when>
<xsl:when test="List/@TemplateType='119'">idHomePageNewWikiPage</xsl:when>
<xsl:otherwise>idHomePageNewItem</xsl:otherwise>
</xsl:choose>
</xsl:with-param>
</xsl:call-template>
</xsl:if>
</xsl:template></xsl:stylesheet>
